3.2.9 · D5Linear Data Structures
Question bank — Priority Queue — concept (heap-based implementation covered later)
This is a companion to the parent concept note: Priority Queue — concept. Every trap here targets a real misconception about what a priority queue promises versus what it does not.
The interface these traps assume
Before catching mistakes, pin down exactly what a priority queue (PQ) offers. Every question below leans on these five operations, so read them once:
The figure below shows the behaviour of the two operations the traps care most about — how insert and extract-min differ on the very same little queue. Notice the coloured arrows: lavender = "just place it, top unchanged", mint = "pull the smallest out".
And this one shows why a PQ is only partially ordered inside (the trap that fools the most people): the coral ring marks the one element whose position is guaranteed — the top — while the two subtrees below it are not sorted against each other.
The size-bounded PQ pattern (referenced by an edge case below)
True or false — justify
A priority queue is an Abstract Data Type — it specifies behaviour (always hand back the most important item), not how the items are stored. Keep that split in mind: many traps below confuse the contract with one particular implementation.
A priority queue always returns elements in fully sorted order if you extract them all
True in output, false in storage. Repeated extract-min does emit a sorted sequence, but the structure never keeps everything sorted internally — only the top is guaranteed placed (see the partial-order figure above).
A priority queue is just a queue, so it must be FIFO
False. It shares the "insert / remove" shape of a Queue (FIFO) but removal is by priority, not arrival time; the word "queue" is loose naming.
Equal priorities always leave in insertion order
False. Standard PQs are not stable (equal priorities have no defined exit order); ties leave in any order unless you attach a sequence counter to break them.
A min-PQ and a max-PQ need two completely different data structures
False. Negating priorities on insert (store ) turns any min-PQ into a max-PQ, so one implementation serves both.
peek and extract-min always return the same element (when the PQ is non-empty)
True at that instant — both look at the current top. The difference is peek leaves it in place while extract-min removes it.
A Heap is required to have a priority queue
False. A heap is one efficient implementation; unsorted or sorted lists also satisfy the PQ contract, just with worse balance of costs.
If insert is then extract-min must also be cheap
False. In an unsorted list insert is precisely because it does no ordering work — so extract-min pays to find the minimum. The cost moves; it does not vanish.
Doing inserts then extracts on a sorted list is as fast as on a heap
False. Sorted-list insert is , giving total, versus the heap's — a huge gap for large .
Merging two array-backed binary heaps must cost
False. You can concatenate the two arrays and run linear-time build-heap on the result, giving . It is re-inserting one by one that would cost ; specialised mergeable heaps push merge down to .
Spot the error
Each statement below contains a subtle mistake. Name it. The two figures at the top of the page give you the concrete imagery — refer back to them.
"A PQ guarantees the whole collection stays sorted after every insert."
The error: it only guarantees the top element's position (the coral-ringed root in the partial-order figure). Keeping everything sorted would cost more per insert unnecessarily — the partial order is the whole point.
"To get the largest item first from a min-PQ, just read whichever item happens to be stored last."
"Stored last" is not part of the abstract PQ contract — there is no addressable last element. The correct trick is to insert so the largest becomes the most-negative minimum, then negate on extraction.
"Ties in a PQ are broken FIFO by default, so I don't need a counter."
PQs are not stable by default (equal priorities have no defined order). Without a pair, tie order is undefined — silently assuming FIFO is the bug.
"A priority queue can only ever remove the minimum, never the maximum."
A PQ is defined as either min-extract or max-extract; the direction is a design choice, not a fixed law.
"Merge just concatenates the two arrays and is instantly done, ."
Raw concatenation may violate the heap ordering, so the result would not answer extract-min correctly. You must still restore the invariant with build-heap, costing — linear, not constant.
"Since Dijkstra uses a PQ, using an unsorted list is fine — insert is ."
Dijkstra's Algorithm does many inserts and many extracts; the extract on an unsorted list makes the whole run , defeating the purpose.
"extract-min on an empty PQ returns 0 (or the smallest possible value)."
An empty PQ has no element to return; the correct behaviour is an error/empty-signal, not a fabricated default value.
"A PQ is a Stack (LIFO) because the most recent important item comes out next."
Order depends on priority, not recency. A newly-inserted low-priority item waits behind older high-priority ones — the opposite of LIFO.
"Merging the two smallest items in Huffman Coding needs the collection sorted, so a PQ sorts it for us."
Huffman only needs the two minimums each step, which extract-min supplies without ever fully sorting the rest — that is why a PQ, not a full sort, is used.
Why questions
Why do we call a priority queue "abstract"?
Because it fixes only the contract (highest-priority item comes out next), leaving storage — list, heap, or tree — as a separate, swappable choice.
Why does making insert cheap tend to make extract expensive (and vice versa)?
Ordering work has to happen somewhere; if you skip it on insert you pay to search on extract, and if you order eagerly on insert extract becomes trivial. The heap spreads the work so both are .
Why is merge sometimes listed as a first-class PQ operation?
Some algorithms repeatedly combine whole queues; a data structure with merge (binomial/leftist/pairing heap) beats re-inserting element by element, which is why merge earns its own name in the interface.
Why can a program store instead of just ?
The pair lets the queue compare by priority first and by insertion order second, giving stable FIFO tie-breaking (defined exit order for equal priorities) without changing the extract logic.
Why is dramatically better than for large inputs?
For , but — roughly 50,000× fewer operations, turning hours into a fraction of a second.
Why does negating priorities convert a min-PQ into a max-PQ?
The most-negative number is the minimum, and it corresponds to the largest original value, so extract-min on hands back the true maximum.
Why is a Heap internally only partially ordered?
It maintains the heap property only along parent-child paths (as the figure shows), which is enough to keep the top correct while avoiding the cost of a full sort.
Why isn't a normal Queue (FIFO) enough when we need "the best option next"?
FIFO answers "who arrived first", a different question from "who matters most"; using arrival order would repeatedly pick the wrong item.
Edge cases
What should peek do on an empty priority queue?
Signal emptiness (error, exception, or null/optional) — there is no top element to look at, so returning a real value would be a lie.
What should merge do when one of the two priority queues is empty?
Return the other one unchanged — the empty PQ contributes nothing, so a correct merge is a no-op in that direction.
If all elements share the same priority, what order do they leave in?
Undefined for a standard PQ (it is not stable); you get some valid order, and only a tie-breaker guarantees FIFO among the equals.
Does a priority queue with exactly one element behave correctly?
Yes — peek and extract both return that lone element, and after extraction the PQ is empty; the contract holds trivially at size 1.
In the top-2 stream trick (size-bounded min-PQ), what happens when the new item is smaller than everything kept?
It is inserted, momentarily becomes the new minimum, and is immediately removed by the size-limiting extract-min — so it never displaces a larger kept item.
Can two elements with identical priority and identical sequence number exist?
No — the sequence counter is unique per insert precisely to make every pair distinct, guaranteeing a total order and deterministic ties.
What is the extract order if you insert priorities in already-sorted order into a min-PQ?
Exactly the same sorted order out; the PQ does not care that input was sorted, it just repeatedly emits the current minimum.
If you extract more times than you inserted, what must happen on the extra calls?
Each extra call finds an empty PQ and must raise an empty/error signal rather than returning a stale or default value.
Connections
- Parent: Priority Queue — concept
- Heap — the efficient implementation whose partial order these traps reference.
- Queue (FIFO) and Stack (LIFO) — the ordering disciplines a PQ is contrasted against.
- Abstract Data Type — why "abstract" matters here.
- Dijkstra's Algorithm and Huffman Coding — the "why a PQ" motivating cases.