Priority Queue —
Highest priority. Always served first.
A priority queue always serves the element with the highest (or lowest) priority, regardless of insertion order. Under the hood it's a heap — a complete binary tree maintained in an array. Watch elements bubble up on insert and bubble down on extract on LearnBug, and the heap structure stops being mysterious.
What is a Priority Queue?
A priority queue is an abstract data type where each element has a priority, and the element with the highest (or lowest) priority is always dequeued first — regardless of when it was inserted. The concrete implementation is almost always a heap: a complete binary tree where every parent is smaller than its children (min-heap) or larger (max-heap).
Why visualization changes everything
Heaps are stored as arrays but logically are trees. On LearnBug you see both simultaneously — the array representation and the tree structure — so when an element bubbles up after insert or sifts down after extract, you watch it move through both views at once. The O(log n) behaviour becomes visually obvious.
Two operations that keep the heap valid
Bubble Up (after insert)
New element is placed at the end of the array. Compare with parent: if smaller (min-heap), swap. Repeat up the tree until heap property is restored. At most log n swaps — the height of the tree.
Sift Down (after extract)
Root (min/max) is removed. Last element is moved to root. Compare with children: if larger than smallest child (min-heap), swap. Repeat down until heap property is restored. Also O(log n).
Insert 5, 3, 8, 1 into a min-heap
Insert 5 — root. Insert 3 — bubble up past 5
3 placed at index 1. Parent is 5 (index 0). 3 < 5 — swap. 3 becomes root.
Heap: [3, 5]
Insert 8 — parent is 3. 8 > 3, no swap needed
8 placed at index 2. Parent is 3. 8 > 3 — heap property satisfied. 8 stays.
Heap: [3, 5, 8]
Insert 1 — bubbles all the way to root
1 at index 3. Parent=5 (index 1). 1 < 5 — swap. Now parent=3 (index 0). 1 < 3 — swap. 1 becomes root.
Heap: [1, 3, 8, 5] | peek() = 1
Extract min (1) — move 5 to root, sift down
Remove 1. Move last element (5) to root. Sift down: 5 vs children 3 and 8. 3 is smaller — swap. Heap restored.
Extracted: 1 | Heap: [3, 5, 8] | Next peek() = 3
Python's heapq — min-heap by default
import heapq
heap = []
heapq.heappush(heap, 5) # O(log n)
heapq.heappush(heap, 3)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)
print(heap[0]) # peek min → 1 (O(1))
print(heapq.heappop(heap)) # extract min → 1 (O(log n))
print(heap[0]) # peek min → 3
# heapify an existing list in O(n)
nums = [5, 3, 8, 1]
heapq.heapify(nums) # [1, 3, 8, 5]# Python only has min-heap. For max-heap: negate values
max_heap = []
for val in [5, 3, 8, 1]:
heapq.heappush(max_heap, -val) # store negated
max_val = -heapq.heappop(max_heap) # negate back → 8
print(max_val) # → 8
# Priority queue with (priority, value) tuples
pq = []
heapq.heappush(pq, (1, 'high priority'))
heapq.heappush(pq, (3, 'low priority'))
heapq.heappush(pq, (2, 'medium'))
print(heapq.heappop(pq)) # → (1, 'high priority')Time & Space Complexity
Frequently asked questions
What is the difference between a heap and a priority queue?
A priority queue is the abstract concept — a data structure where the highest priority element is always accessible. A heap is the concrete implementation. You could implement a priority queue with a sorted array (O(n) insert, O(1) access) or an unsorted array (O(1) insert, O(n) access). The heap gives O(log n) for both — the best general trade-off.
Why is heapify O(n) but n pushes is O(n log n)?
Heapify works bottom-up, sifting down from each internal node. Most nodes are near the bottom and sift only a short distance. The mathematical sum of work at each level collapses to O(n). Individual pushes each take O(log n), giving O(n log n) total — significantly worse for large inputs.
What are common interview problems using priority queues?
K Largest Elements (LC 215), Merge K Sorted Lists (LC 23), Top K Frequent Elements (LC 347), Find Median from Data Stream (LC 295 — two heaps), Task Scheduler (LC 621), Dijkstra's shortest path (uses a min-heap), and Kth Closest Points to Origin (LC 973). The heap pattern appears constantly in problems involving "top K" or "minimum/maximum at every step".
How do I use a priority queue for Dijkstra's algorithm?
Push (distance, node) tuples. Always pop the smallest distance node next. When you find a shorter path to a neighbour, push the new (shorter_distance, neighbour) — don't update in place (heapq doesn't support O(log n) updates). Old entries for the same node are skipped using a visited check.
What is the two-heap trick for finding the running median?
Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half. Keep them balanced (sizes differ by at most 1). The median is always the top of the larger heap, or the average of both tops. This gives O(log n) per insertion and O(1) median access — LeetCode 295.
Watch elements bubble up and sift down in your heap
Paste your priority queue operations into LearnBug and see every heap adjustment animated step by step.