A binary heap is a complete binary tree where every parent satisfies the heap property. Min-heap: parent ≤ children (min at root). Max-heap: parent ≥ children.
Stored as an array — for index i: left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
Python’s heapq is always a min-heap. For a max-heap: negate values when pushing, negate again when popping.
Priority Queue Applications
Application
How heap helps
Dijkstra’s shortest path
Always process the nearest unvisited node
Huffman encoding
Always merge the two least-frequent symbols
Task scheduler
Always run the highest-priority job next
Merge k sorted lists
O(n log k) using a min-heap of size k
Heap Sort
Heap sort: heapify in O(n), then pop n times each O(log n) = O(n log n) total, O(1) extra space.
defheapsort(arr):
heapq.heapify(arr) # O(n)return [heapq.heappop(arr) for _ in arr] # O(n log n)print(heapsort([3,1,4,1,5,9])) # [1,1,3,4,5,9]
Practice
1. Find the k largest elements in an array efficiently.
import heapq
def k_largest(arr, k):
return heapq.nlargest(k, arr) # O(n log k) internally
# Or: maintain a min-heap of size k; push each element;
# if heap exceeds k, pop the min. Final heap = k largest.
2. Why is heapify O(n) even though it builds a heap from n elements?
Naive: n insertions each O(log n) = O(n log n).
Heapify works bottom-up: sift-down from the last internal node to the root.
Most nodes are near the bottom and need only a few swaps.
Mathematical sum: sum of (height × nodes at that height) = O(n).
Knowledge Check
In a min-heap, the minimum element is always
Correct — the heap property guarantees the root is the smallest.
The last index holds a leaf, not necessarily the minimum.
That's approximately the boundary between internal nodes and leaves.
The min is always at the root; other elements are only partially ordered.
Recap: min-heap root = minimum. This is why heappop() gives you the minimum in O(log n) — remove root, fix heap.
heapq.heappush and heappop are both
heappop requires sifting down — O(log n).
Correct — both operations may need to sift up or down the height of the heap.
Heaps are trees; operations take height = log n steps.
That's the total complexity of n pops.
Recap: heap height = log n. Push = sift up (at most log n swaps). Pop = remove root, put last element at root, sift down (at most log n swaps).
Python's heapq module implements
Python heapq is a min-heap. Negate values for max-heap behaviour.
Correct — the minimum is always at index 0.
heapq is a heap, not a sorted list; only the minimum is guaranteed at index 0.
Heaps and BSTs are different structures; heaps don't support efficient search.
Recap: heapq = min-heap. For max-heap: push -x, pop and negate. Or use heapq.nlargest(k, iterable).
Heap sort's worst-case time complexity is
That's bubble sort/insertion sort worst case.
Correct — heapify O(n) + n pops each O(log n) = O(n log n).
O(n) sorting is only possible with non-comparison sorts (counting, radix).
Can't sort n items faster than O(n) just to read them all.
Recap: heap sort = O(n log n) worst case, O(1) extra space. Not stable (equal elements may reorder). In practice quicksort is faster due to cache behaviour.
A priority queue is most suitable for
That's a plain queue.
Correct — priority queue extracts the min/max each time, regardless of insertion order.
Priority queues don't support indexed access.
Use a hash set for duplicate detection.
Recap: priority queue = 'give me the best item' each time. Dijkstra's, Prim's MST, Huffman coding, A* search all rely on this.