Exercises — Priority Queue — concept (heap-based implementation covered later)

Priority Queue. A Stack (LIFO) returns the most recently added item; a Queue (FIFO) returns the earliest added item. Neither looks at urgency. The phrase "most-urgent job" means removal order depends on a priority number, not on arrival time — that is exactly the priority-queue contract.

peek() returns milk (priority 3, the smallest). The queue is unchanged — peek only looks. The contents stay {tea:7, milk:3, ice:9}. Only extract-min would remove milk. (If the queue had been empty, peek() would have nothing to return — see the empty-queue [!mistake] at the top.)

A min-PQ, with frequency as the priority. "Least-frequent" = smallest frequency number = smallest priority = what extract-min hands back. Two extract-min calls give you the two rarest symbols to merge.

After all inserts: {A:5, B:1, C:4, D:1, E:9}.

• extract-min → smallest priority is 1, held by both B and D. Standard PQs are not stable (parent's third [!mistake]), so a tie may return either. We'll assume insertion-order tie-break gives B(1) first. State: {A:5, C:4, D:1, E:9}.
• extract-min → D(1). State: {A:5, C:4, E:9}.
• extract-min → smallest is C(4). State: {A:5, E:9}.

Out (in order): B, D, C. Note E(9), inserted last, is nowhere near leaving — priority beats arrival.

Insert each price p as -p (parent Example 2): insert $-40$, $-10$, $-70$, $-25$. State (by priority): {-70, -40, -25, -10}. extract-min returns the smallest stored number = $-70$. Un-negate: $-(-70)=70$. Result: 70, which is indeed the largest original price. Why it works: the most-negative stored value corresponds to the most-positive real value.

Mirror the parent's Example 3 technique — the tiny min-PQ throws away the smallest whenever it overflows, so the two largest survive. (We only ever extract-min right after an insert pushed size to 3, so the queue is never empty when we extract — safe by construction.)

• insert 8 → {8}
• insert 2 → {2,8}
• insert 10 → {2,8,10} size 3 → extract-min removes 2 → {8,10}
• insert 6 → {6,8,10} → extract-min removes 6 → {8,10}
• insert 4 → {4,8,10} → extract-min removes 4 → {8,10} Remaining: {8, 10} — the top-2 largest. ✅

From the parent's cost table:

• Unsorted list: insert $O(1)$, each extract-min $O(n)$ → total $\approx 10^6\times 1000=10^9$ scans.
• Sorted list: one-time sort/insert cost, each extract-min $O(1)$ → total $\approx 10^6\times 1=10^6$ operations. Sorted list wins, by roughly a factor of $n=1000$ per extract. When extracts vastly outnumber inserts, pay once to keep sorted so every extract is cheap.

Using the parent's derivation: $\text{Unsorted: }n\cdot O(1)+n\cdot O(n)=O(n^2)$ $\text{Sorted: }n\cdot O(n)+n\cdot O(1)=O(n^2)$ $\text{Heap: }n\cdot O(\log n)+n\cdot O(\log n)=O(n\log n)$ Plugging $n=4096$, ${\log }_{2}n=12$:

• $n^2=4096^2=16,777,216$ (both naive options).
• $n{\log }_{2}n=4096\times 12=49,152$ (heap). Ratio: $16,777,216/49,152\approx 341$. The heap is about 341× faster here — and the gap widens with $n$.

The figure below plots both curves against $n$. The orange curve is the naive $n^2$ cost; the teal curve is the heap's $n{\log }_{2}n$. The dashed plum line marks $n=4096$: read up to where each curve crosses it — the orange point sits at 16.8 million, the teal point barely above the axis at 49 thousand. That vertical gap is the 341× speed-up, and notice how it opens ever wider as you slide the plum line rightward.

The unsorted list is cheap only for insert; every extract-min must scan all $n$ elements to find the minimum, costing $O(n)$. In a mixed workload with many extracts, those scans dominate and the cheap insert becomes irrelevant. Each naive structure buys one fast operation by making the other slow — total stays $O(n^2)$. A Heap refuses that trade: by keeping only a partial order (top guaranteed, rest loosely arranged), both operations become $O(\log n)$, so the whole workload is $O(n\log n)$.

Use the parent's mnemonic "P for priority, S for sequence": store the pair $(p,\text{seq})$ where seq is a global counter incremented on every insert. Compare pairs lexicographically (dictionary rule above) — first by $p$, then by seq. Re-doing the ties from L2.1: B was inserted (seq 2), D was inserted (seq 4). Both have $p=1$, so the queue compares $(1,2)$ vs $(1,4)$; the first entries tie, so we compare seconds: since $2<4$, B leaves before D — guaranteed, not by luck. Every tie is now deterministic FIFO because seq is unique and increasing.

Maintain two min-PQs over the same patients:

• PQ_urgent — stores triage p as-is. extract-min gives the most urgent (smallest p).
• PQ_relaxed — stores triage as -p (negation trick, L2.2). extract-min there gives $-(\max p)$, i.e. the least urgent patient. insert(patient, p): push (p) to PQ_urgent and (-p) to PQ_relaxed. To report most/least urgent, peek the matching queue (guarding for emptiness first — see the top [!mistake]). When you actually remove a patient you must invalidate them in the other queue — commonly with a "lazy deletion" tombstone, checked on peek. This reuses one primitive — a min-PQ — to serve both extremes, echoing Example 2 of the parent.

Seed the PQ with the front of each list, tagged with which list it came from. Repeatedly extract-min, output it, and push the next element of that same list. (We stop the moment the PQ is empty — the empty-queue guard from the top is the loop's exit condition.)

• Seed: {L1:2, L2:1}.
• extract 1 (from L2) → out [1]; push L2's next 4 → {L1:2, L2:4}.
• extract 2 (L1) → out [1,2]; push L1's next 5 → {L1:5, L2:4}.
• extract 4 (L2) → out [1,2,4]; push L2's next 4 → {L1:5, L2:4}.
• extract 4 (L2) → out [1,2,4,4]; push L2's next 7 → {L1:5, L2:7}.
• extract 5 (L1) → out [1,2,4,4,5]; push L1's next 9 → {L1:9, L2:7}.
• extract 7 (L2) → out [...,7]; L2 empty → {L1:9}.
• extract 9 (L1) → out [...,9]; queue empty → stop. Output: [1, 2, 4, 4, 5, 7, 9]. ✅ (This is the heart of k-way merge; with $k$ lists you keep $k$ fronts.)

Argument. In a flat list the minimum must live at a known position (say, one end) for extract to be $O(1)$. Keeping it there after an arbitrary insert requires placing the new element in its correct relative slot, which may force shifting up to $n$ elements → insert is $\Omega (n)$. Conversely, if insert is $O(1)$ (append anywhere), the minimum's position is unknown, so extract must search all $n$ elements → extract is $\Omega (n)$. A single ordering promise can't make both cheap: fast extract needs order maintained (slow insert); fast insert abandons order (slow extract). Escape. A Heap is not flat — it's a Binary Tree (a complete one). Its height is only ${\log }_{2}n$ because each level doubles the number of nodes, so $n$ nodes fit in about ${\log }_{2}n$ levels (see the tree figure below). Both insert (bubble-up) and extract (sink-down) touch only one root-to-leaf path = $O(\log n)$ each. The tree's branching is exactly what breaks the flat-list dilemma.

Inserting the $k$-th item into a heap of size $k$ costs $O(\log k)$, so the total is ${\sum }_{k=1}^{n}O({\log }_{2}k).$ Why the bound ${\sum }_{k=1}^n{\log }_{2}k\le n{\log }_{2}n$ holds: the sum has exactly $n$ terms. Since ${\log }_2$ is an increasing function and every index $k$ satisfies $k\le n$, each term ${\log }_{2}k$ is at most the largest term ${\log }_{2}n$. Replacing all $n$ terms by that common largest value can only increase the sum: ${\sum }_{k=1}^n{\log }_{2}k\le \underset{n\text{ copies}}{\underbrace{{\log }_{2}n+{\log }_{2}n+\cdots +{\log }_{2}n}}=n{\log }_{2}n.$ Hence the build is $O(n\log n)$. For $n=1024$, ${\log }_{2}1024=10$, so the upper bound is $1024\times 10=10,240$ operations. (Aside: a smarter bottom-up heapify achieves $O(n)$, but the repeated-insert $O(n\log n)$ bound is what we asked for here.)

A min-PQ pops the smallest tuple under the lexicographic (dictionary) rule from L4.1, so every field must be arranged so that "should-run-sooner" translates into "numerically smaller." Go rule by rule:

• Rule 1 — importance: bigger $I$ must run first, but a min-PQ prefers smaller numbers. So store $-I$: a bigger $I$ becomes a more negative (smaller) key, winning. This is the primary key.
• Rule 2 — deadline: among equal importance, smaller $d$ runs first — and min-PQ already prefers smaller, so store $d$ as-is. This is the secondary key, only consulted when the $-I$ values tie.
• Rule 3 — FIFO: among equal deadline, earlier insert wins; seq grows with time, so smaller seq = earlier, stored as-is. This is the tertiary tie-breaker.

Stored key (compared lexicographically): $(-I,d,\text{seq})$

Verify with the samples — build each key, then find the lexicographically smallest first:

• T1 → $(-5,20,1)$
• T2 → $(-5,10,2)$
• T3 → $(-9,99,3)$

Compare first entries: T3 has $-9$, which is smaller than $-5$, so T3 pops first (it is the most important, $I=9$). T1 and T2 both start with $-5$ (importance tie), so we drop to the second entry — the deadline: $10<20$, so T2 before T1. Run order: T3 → T2 → T1. Every rule fired at the right priority level, and the design generalises: add more tie-break fields simply by appending them to the tuple in order of importance. ✅