Stack/QueueData structureaka heap queue, PQ

Priority Queue

An abstract queue where the element with the highest (or lowest) priority is always removed first, typically backed by a binary heap.

▶ Visualize Pattern: Heap / Priority Queue Practice (8)

Progress

Definition

A priority queue is an abstract data type supporting insert(x, priority) and extractMin() / extractMax(). Unlike a FIFO Queue, removal order is determined by priority, not arrival.

The standard implementation is a Binary Heap: a complete binary tree stored in an array where each parent is ≤ its children (min-heap). Insert and extract cost O(log n); peeking the top is O(1). Alternatives include Fibonacci Heap (better amortized decreaseKey) and balanced BSTs.

Priority queues drive Dijkstra's Algorithm, Prim's Algorithm, Heap Sort, Huffman Coding, k-way merging, event simulation, and every "top-k" or "k-th largest" problem.

heapO(log n)greedyDijkstratop-k

Intuition

A mental model before the formal terms.

A hospital emergency room: patients are not treated in arrival order but by severity. The triage nurse keeps the most critical patient ready at the front without fully sorting everyone — new arrivals only need to be compared with a few others to find their place.

A heap is like a tournament bracket in which the winner sits at the top. Removing the winner triggers a short re-match down one path of the bracket, not a full re-tournament.

How it works

Store elements in an array h; the children of index i are 2i+1 and 2i+2, the parent is (i-1)/2.
push(x): append x at the end, then sift up: swap with the parent while x is smaller than it.
pop(): save h[0], move the last element to index 0, then sift down: swap with the smaller child while a child is smaller.
peek(): return h[0].
For a max-priority queue, negate the keys or flip the comparator.

Why it works

The heap invariant (parent ≤ children) implies the root is the global minimum. Sift-up and sift-down each fix exactly one violated edge per step and move one level, so they restore the invariant in O(height) = O(log n).

Storing a complete tree in an array with index arithmetic means no pointers, perfect cache behaviour, and O(1) access to parent/children.

Operations

Operation	Description	Cost
push(x)	Insert with sift-up.	O(log n)
pop()	Remove the minimum with sift-down.	O(log n)
peek()	Return the minimum without removing it.	O(1)
heapify(array)	Build a heap in place from an array.	O(n)
decreaseKey(i, k)	Lower a key and sift up (needs index handles).	O(log n)
size() / isEmpty()	Count of stored elements.	O(1)

Recognition

How to tell a problem wants this.

The problem asks for the k largest/smallest, k-th largest, top-k frequent, or the median of a stream.
You repeatedly need the current minimum/maximum while inserting new items: shortest paths, MST, scheduling by deadline or frequency.
Merging k sorted lists or streams.
"Process the most urgent/cheapest/earliest task next" — greedy with a dynamic candidate set.

“k most frequent” → Heap / Priority Queue “weighted graph” → Shortest Path (Weighted)“maximum number of non-overlapping” → Greedy

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Binary Heap visualization.

Commands — "insert N" or "extract", separated by commas

Empty tree

Heap array (level order)

empty

1/45Empty min-heap. Invariant: every parent ≤ its children, and the tree is complete, so it can live in an array with parent(i) = (i−1)/2.

Newly insertedElement being siftedCompared withSwappedExtracted minimum

PseudocodeLearn Binary Heap →

1insert(x): append x at the end; i = n-1
2  while i > 0 and heap[i] < heap[parent(i)]: swap; i = parent(i)   # sift up
3extract(): min = heap[0]; move last element to the root; n -= 1
4  i = 0; while smallest child < heap[i]: swap with the smaller child; continue   # sift down
5parent(i) = (i-1)//2, children = 2i+1, 2i+2

Variables

Complexity

access O(1)

search O(n)

insert O(1)

delete O(log n)

Speed

Pseudocode

1class MinPQ:
2  h = []
3  push(x): h.append(x); siftUp(len - 1)
4  pop(): top = h[0]; h[0] = h.removeLast(); siftDown(0); return top
5  siftUp(i): while i > 0 and h[i] < h[parent(i)]: swap; i = parent(i)
6  siftDown(i): loop: c = smaller child; if h[c] < h[i]: swap; i = c else break

Implementation

1from typing import Callable, Generic, TypeVar
2 
3T = TypeVar("T")
4 
5 
6class PriorityQueue(Generic[T]):
7    """A min-priority-queue over a binary heap stored in a list. The standard
8    library already ships this as heapq (a min-heap over a plain list); this
9    shows the machinery heapq hides."""
10 
111 · State: the heap list and the comparator ("higher priority" = less)
12    def __init__(self, higher_priority: Callable[[T, T], bool] = lambda a, b: a < b) -> None:
13        self._heap: list[T] = []
14        self._higher_priority = higher_priority
15 
16    def __len__(self) -> int:
17        return len(self._heap)
18 
19    def peek(self) -> T:
20        if not self._heap:
21            raise IndexError("peek on empty priority queue")
22        return self._heap[0]
23 
242 · push: append at the end, then sift the newcomer up to its level
25    def push(self, value: T) -> None:
26        self._heap.append(value)
27        self._sift_up(len(self._heap) - 1)
28 
293 · pop: the root is the answer; move the last element into it and sift down
30    def pop(self) -> T:
31        if not self._heap:
32            raise IndexError("pop on empty priority queue")
33        best = self._heap[0]
34        last = self._heap.pop()
35        if self._heap:
36            self._heap[0] = last
37            self._sift_down(0)
38        return best
39 
404 · _sift_up: swap with the parent while the child outranks it
41    def _sift_up(self, i: int) -> None:
42        heap = self._heap
43        while i > 0:
44            parent = (i - 1) // 2
45            if not self._higher_priority(heap[i], heap[parent]):
46                break
47            heap[i], heap[parent] = heap[parent], heap[i]
48            i = parent
49 
505 · _sift_down: swap with the better child while a child outranks the node
51    def _sift_down(self, i: int) -> None:
52        heap = self._heap
53        n = len(heap)
54        while True:
55            best, l, r = i, 2 * i + 1, 2 * i + 2
56            if l < n and self._higher_priority(heap[l], heap[best]):
57                best = l
58            if r < n and self._higher_priority(heap[r], heap[best]):
59                best = r
60            if best == i:
61                break
62            heap[i], heap[best] = heap[best], heap[i]
63            i = best

Walkthrough

heap = self._heap binds the list to a local at the top of both sift methods — attribute lookup is a dict probe in CPython, and this removes it from the inner loop.
heap[i], heap[parent] = heap[parent], heap[i] is the tuple-packing swap; it needs no temporary and is a single bytecode sequence.
(i - 1) // 2 uses floor division, which is correct here because the while i > 0 guard keeps the numerator non-negative.
__len__ makes len(pq) and truthiness (if pq:) work, which is the Pythonic way to expose size rather than a size() method.
The comparator defaults to lambda a, b: a < b, so the queue is a min-queue over anything that defines __lt__ — exactly the contract heapq relies on.

Complexity (this implementation)

time O(log n) push and pop, O(1) peek · space O(n)

The comparator is a Python-level call, so this class is several times slower than heapq, whose sift loops are implemented in C.

Language notes

heapq is the production answer: heappush, heappop and heapify operate on a plain list and are written in C — this class exists to show what they do.
heapq is a MIN-heap with no comparator parameter; the standard workarounds are pushing (-priority, item) for a max-heap or (priority, tiebreak, item) tuples for custom ordering.
heapq.heapify(lst) is Floyd O(n) construction, far better than n individual pushes when you already have all the elements.
heapq.nsmallest/nlargest handle top-k directly and switch strategy based on k versus n.

Common mistakes in this language

Pushing tuples whose second element is not comparable ((priority, some_object)): when priorities tie, Python falls through to comparing the objects and raises TypeError.
Assuming heapq gives a max-heap — it does not, and negating priorities is the standard fix (which breaks for non-numeric priorities).
Calling self._heap.pop(0) instead of pop(), which removes the root, is O(n), and destroys the heap encoding.

Language differences that matter here

Standard library: Python has heapq (min-heap over a list) and C++ has std::priority_queue plus the *_heap algorithms (max-heap by default) — JavaScript and TypeScript have nothing, so the class above is not a teaching exercise there, it is the implementation.
Default orientation is the classic cross-language trap: heapq is a min-heap, std::priority_queue is a max-heap. Code ported between them silently returns the wrong extreme.
Custom ordering: C++ takes a comparator as a template parameter (inlined, zero cost), JS/TS take a closure (a real call per comparison), and heapq takes none at all — you encode the order into the pushed value, usually as a tuple.
Failure on empty: C++ std::priority_queue::top() is undefined behaviour on an empty queue, Python heapq.heappop raises IndexError, and the JS/TS classes here throw RangeError by choice — there is no shared convention.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Top element only.
Search	O(n)	O(n)
Insert	O(log n)	O(log n)	O(1) average for random keys.
Delete	O(log n)	O(log n)	Top only; arbitrary delete needs an index map.
Update	O(log n)	O(log n)	decreaseKey / increaseKey with index handles.
Push	O(log n)	O(log n)
Pop	O(log n)	O(log n)
Peek	O(1)	O(1)
Heapify	O(n)	O(n)
Space	O(n)

Advantages & disadvantages

Advantages

O(log n) insert and extract, O(1) peek, O(n) heapify — the best general-purpose trade-off.
Array-backed, allocation-free, cache-friendly.
Simple enough to write from scratch in an interview in ~25 lines.

Disadvantages

No efficient search or arbitrary delete without an auxiliary index map.
Not sorted: iterating the underlying array gives no useful order.
decreaseKey requires tracking positions; many implementations instead push duplicates and lazily discard stale entries.

Use cases

Dijkstra and Prim (extract cheapest frontier edge).
Top-k and k-th largest queries, streaming medians (two heaps).
Task scheduling by deadline, priority, or frequency (task scheduler, CPU schedulers).
Merge k sorted lists, Huffman coding, event-driven simulation.

Use it when

You repeatedly need the smallest or largest element while the set changes.
Top-k / k-th largest from a stream with O(n log k) time and O(k) space.
Greedy algorithms whose candidate set grows dynamically (Dijkstra, Prim, Huffman, scheduling).

Avoid it when

You need the extreme of a sliding window — a Monotonic Queue does it in O(1) per step.
You need sorted iteration, predecessor/successor, or arbitrary deletion — use a balanced BST (AVL Tree, Red-Black Tree).
All priorities are known up front and there are no inserts after building — just sort once.
Priorities are small integers — a bucket array gives O(1) operations.

Alternatives

Binary Heap Fibonacci Heap AVL Tree Monotonic Queue Queue

Compare: Heap vs Priority Queue

Common mistakes

Popping into an empty heap, or moving the last element to the root when it *was* the root (heap of size 1) and then sifting a stale value.
Using a max-heap when a min-heap is needed for "k largest" (keep a min-heap of size k; its top is the k-th largest).
Trying to decreaseKey in Dijkstra without index handles — push a new entry instead and skip stale ones on pop.
Comparing tuples with non-comparable payloads in Python ((dist, node_object)) — add a tiebreaker counter.
Assuming heapq is a max-heap or that Java PriorityQueue.iterator() yields sorted order.

Interview patterns

K-th largest element: min-heap of size k, O(n log k).
Top-k frequent elements: count with a hash map, then heap of size k on frequency.
Median from a data stream: max-heap for the lower half, min-heap for the upper half, keep sizes balanced.
Merge k sorted lists: heap of (value, list index), pop and push the successor.
Task scheduler / reorganize string: greedily take the most frequent remaining item, with a cooldown queue.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
Where does O(n log n) come from?Beginner
Top K from a streamIntermediate
When a hash map is the wrong choiceIntermediate

Mock interviews

Kth Largest Element in an ArrayIntermediate
Network Delay TimeAdvanced
Merge IntervalsIntermediate

Interview problems

Merge k Sorted Listshard Kth Largest Element in an Arraymedium Top K Frequent Elementsmedium Kth Largest Element in a Streameasy Find Median from Data Streamhard Task Schedulermedium Meeting Rooms IImedium Network Delay Timemedium

Don't delegate understanding

The manifesto →

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related