Priority queues
Only the front element is promised. The heap underneath keeps the winner at the root and leaves everything else loosely arranged, which is exactly why it costs less than keeping the collection sorted.
A hospital waiting room, not a ticket queue. Nobody puts everyone in a full running order, because the staff only ever need to know who is worst right now — and one quick shuffle after each patient is called keeps that answer correct, the same way a glance down the row would.
Most confusion about priority queues comes from expecting one and getting the other of two different things. People reach for a priority queue wanting a collection that is always sorted, and what they get is a collection that always knows its winner. That is a much weaker promise, it is cheaper for exactly that reason, and nearly every surprising thing a priority queue does traces back to the gap between those two.
Only the front is promised#
Underneath a priority queue is a heap, and a heap is a rule about parents and children rather than a rule about the sequence. Python’s own documentation writes the rule as plainly as it can be written: for a min-heap held in a list, heap[k] is no greater than heap[2k+1] and , for every k where those children exist. Every node is smaller than both of its children, and nothing at all is said about siblings, or cousins, or any two items that do not sit one directly above the other.heap[2k+2]
Follow that rule up the tree and you get the one guarantee the structure exists to make. If every parent beats its children, then the root beats its children, which beat theirs, all the way down — so the root beats everything. Python’s documentation puts the consequence in one line: the smallest element is always the root, heap[0]. That is the whole promise. Not that the second-smallest is at position one, which is not true, and not that the array is nearly sorted, which is also not true.
The tree is a picture rather than a construction. The items live in a plain array, and the parent-child links are arithmetic on the indices — position k has its children at 2k+1 and 2k+2 — so there are no nodes and no pointers to chase, which is one reason a heap performs so much better than the pointer-hopping a linked list commits you to. Python’s documentation notes that this makes the heap readable as an ordinary list without surprises, and that sorting one leaves the heap rule intact — a sorted array satisfies the parent-child rule trivially, which is worth sitting with for a second, because it shows how much slack the rule leaves.
Why the loose arrangement is the point#
A sorted list can answer any question about order, and pays for that on every insertion by finding the one correct position among n. A heap answers a single question and pays much less, because it never decides anything it was not asked. Two items that will never compete to be the winner can sit in either arrangement forever, and no operation will ever need to know which of them is bigger.
Removing the winner shows the saving directly. Take the root away and the array has a hole at the front, so the last item is moved into it and then swapped downward — against the smaller of its two children each time — until the parent-child rule holds again. That path is the height of the tree, and because the tree stays balanced by construction, the height is logarithmic in the number of items. Java documents exactly this shape for its own implementation: O(log n) for the enqueuing and dequeuing methods, and constant time for peek, element and size.
That constant-time peek is the payoff and the reason schedulers and event loops are built on this structure. Asking “what is next” is free; you pay only when you actually take it.
Where it goes wrong#
The mistake almost everybody makes once is iterating a priority queue and expecting priority order. Java’s documentation is explicit that the iterator and spliterator are not guaranteed to traverse in any particular order, and the reason is the one this page started from: there is no order in there to traverse. What comes out is the backing array as it happens to be arranged, which will usually start with the right element and then wander, because the smallest item really is first and nothing after it was ever sorted. That is the worst possible failure shape — right often enough to pass a small test, wrong as soon as the data grows.
The second trap is searching. Java documents linear time for remove(Object) and contains(Object), sitting right beside the logarithmic operations, and the difference is not an implementation detail to be optimised away later. A heap has no idea where a non-winning item sits, so finding one means looking at all of them. Code that cancels scheduled work by removing it from the queue is doing a full scan every time, and that is easy to miss precisely because the neighbouring operations are so cheap.
The third is mutating an item’s priority after it has been added. The heap put it where it belongs using the value it had at insertion, and nothing goes back to re-examine it — so changing that value leaves a collection that no longer satisfies its own rule, with no error raised and no operation that will notice. It is the same failure mode as a search tree whose ordering rule quietly breaks: the structure still works, still returns answers, and the answers are wrong. Remove and re-add instead, or push a fresh entry and discard stale ones as they surface.
IF YOU REMEMBER ONE THING
A heap keeps one promise — the winner is at the root — and buys its speed by refusing to make any of the others. Every surprise on this page is that refusal, met somewhere it was not expected.
Questions people also ask
5 QUESTIONSWhy does printing a priority queue give me the wrong order?
Because it was never in order. Java's documentation states outright that the iterator and spliterator are not guaranteed to traverse the elements in any particular order — the structure underneath is a heap, which only ever arranges enough to keep the winner at the root. Printing it shows you the array as it happens to be laid out. The only ordered way to read a priority queue is to keep taking from the front until it is empty.
Is a priority queue the same as a sorted list?
No, and the difference is the entire reason it is worth using. A sorted list answers every positional question and pays to maintain a total order on each insertion. A heap answers exactly one question — what is the smallest item — and pays far less, because it never has to decide the relative order of two items that are not competing to be the winner.
What does it cost to add and remove?
Java documents O(log n) for the enqueuing and dequeuing methods — offer, poll, add and remove — constant time for peek, element and size, and linear time for remove(Object) and contains(Object). That last pair is the one people miss: searching a heap for an arbitrary value has no shortcut, because the structure says nothing about where a non-winning item sits.
Can I change an item's priority after adding it?
Not through the standard interface, and doing it by mutating the object in place is a bug rather than a shortcut. The heap placed that item using the value it had at insertion time, and nothing re-examines it afterwards, so the collection quietly stops satisfying its own ordering rule. The usual fixes are to remove and re-add the item, or to add a fresh entry and ignore anything stale when it comes out.
Does a priority queue handle ties?
Not in any way you should depend on. Two items that compare as equal can come out in either order, and nothing in the structure records which arrived first. If insertion order matters among equals, the standard fix is to make it part of the comparison — a counter that increases on every insertion, compared after the real priority.