Queue, Deque, and PriorityQueue

import java.util.*;

public class TwoFamilies {

    // "poll", "peek", "remove" or "element" on an EMPTY queue.
    // Return "null" or "NoSuchElementException". Predict all four first.
    static String tryOnEmpty(String method) {
        return "null"; // TODO
    }

    // Offer job1 and job2. Return: what peek gave, the size after,
    // what poll gave, the size after that. Four strings.
    static List<String> peekThenPoll() {
        return List.of(); // TODO
    }

    // Empty is NORMAL here. Take everything, stop when it runs out.
    static List<String> drainQuietly(Queue<String> q) {
        return List.of(); // TODO
    }

    // Empty means a BUG here. Pick the method that says so.
    static String mustHaveOne(Queue<String> q) {
        return null; // TODO
    }

    public static void main(String[] args) {
        // TODO: print all four empty-queue results
        // TODO: show peek does not remove and poll does
    }
}

import java.util.*;

public class NotSorted {

    static PriorityQueue<Integer> queue() {
        return new PriorityQueue<>(List.of(50, 10, 40, 20, 30));
    }

    // The order a for-each loop gives you. This is NOT sorted order.
    static List<Integer> walkOrder(PriorityQueue<Integer> pq) {
        return List.of(); // TODO
    }

    // Poll everything out. THIS is sorted order.
    static List<Integer> pollOrder(PriorityQueue<Integer> pq) {
        return List.of(); // TODO
    }

    // Check by index: for every i, the values at 2i+1 and 2i+2 must not be smaller.
    static boolean heapRuleHolds(List<Integer> internal) {
        return false; // TODO
    }

    // A sorted list, with the queue still holding everything afterwards.
    static List<Integer> sortedWithoutEmptying(PriorityQueue<Integer> pq) {
        return List.of(); // TODO
    }

    public static void main(String[] args) {
        // TODO: print the walk order and the poll order and compare them
        // TODO: check the heap rule on the walk order
    }
}

import java.util.*;

public class MiniHeap {

    private int[] a = new int[16];
    private int size;
    private long comparisons;

    private static int parent(int i) { return (i - 1) / 2; }
    private static int left(int i)   { return 2 * i + 1; }
    private static int right(int i)  { return 2 * i + 2; }

    // Put it at the end, then sift up while it is smaller than its parent.
    // Grow the array first if it is full. Count every comparison.
    public void offer(int v) {
        // TODO
    }

    // Take the root, move the last value into its place, then sift down.
    public int poll() {
        return 0; // TODO
    }

    public int peek() {
        return 0; // TODO
    }

    public int size() {
        return size;
    }

    public long comparisons() {
        return comparisons;
    }

    // A copy of the used part, so you can watch the shape change.
    public int[] internal() {
        return Arrays.copyOf(a, size);
    }

    public static void main(String[] args) {
        // TODO: offer 20 random numbers, printing internal() after each one
        // TODO: poll them all and confirm the output is sorted
        // TODO: count comparisons for 1_000_000 offers and compare with n log n
    }
}

import java.util.*;

public class Triage {

    record Request(String unit, int urgency, int arrivalOrder) { }

    static List<Request> incoming() {
        return List.of(
                new Request("Atlas",  3, 1),
                new Request("Beacon", 9, 2),
                new Request("Cipher", 3, 3),
                new Request("Drift",  7, 4));
    }

    // A plain FIFO queue. Return the unit names in the order served.
    static List<String> inArrivalOrder(List<Request> requests) {
        return List.of(); // TODO
    }

    // Highest urgency served first.
    static List<String> byUrgency(List<Request> requests) {
        return List.of(); // TODO
    }

    // A PriorityQueue with nothing to compare by. Return "ok" or the exception name.
    static String withoutTellingItHowToCompare(List<Request> requests) {
        return "ok"; // TODO
    }

    // Highest urgency first, and ties broken by who arrived first.
    static List<String> byUrgencyThenArrival(List<Request> requests) {
        return List.of(); // TODO
    }

    public static void main(String[] args) {
        // TODO: print all four and compare them
    }
}