learningto/pass

Heaps / Priority Queues

IntermediateData Structures

Heaps efficiently maintain the max or min element. Python's heapq is a min-heap. The top-K pattern and merge-K-sorted-lists are classic Google questions.

AVG TIME
O(log n)
SPACE
O(n)
BEST
O(1)
WORST
O(log n)

Key Concepts

  • 1Python heapq is min-heap; negate values for max-heap behavior
  • 2Top-K elements: maintain heap of size K, O(n log k)
  • 3heapq.heapify() builds heap from list in O(n)
  • 4heapq.nlargest/nsmallest for one-off queries
  • 5Merge K sorted lists: push (val, list_idx, element_idx) tuples

In Python

Concept to Code- 1 structure for this topic
import required:import heapq
declare
h = []
heapq.heapify(h)
common ops
heapq.heappush(h, x)
O(log n)
heapq.heappop(h)
O(log n)
h[0]
O(1)
heapq.heapify(lst)
O(n)
say in interview
"I'll use a min heap to always get the smallest element in O(log n)"
Python's heapq is min-heap only. For max-heap, negate values: heappush(h, -val). Or use heapq.nlargest().

Math You Need For This

A sorting funnel. You pour items in the top and the smallest always floats to the tip. The funnel has log(n) levels, so settling an item into place takes log(n) swaps.

Required concepts
Key math ideas
1 / 2

Logarithms - "how many times can you cut in half?"

log₂(n) answers this question: if you start with n things and keep cutting the group in half, how many cuts until you reach 1? For 1,024 items that is only 10 cuts. For a million items it is about 20. The number barely grows even as n explodes.

Remaining1024 items (log₂(1024) = 10)
Clicks so far: 0

Think of it this way: A phone book with 1,024 names. Flip to the middle - is your name before or after? Flip to the middle of the surviving half. Repeat. You find any name in at most 10 flips, not 1,024.

For algorithms: Any algorithm that cuts its remaining work in half each step runs in O(log n). Binary search, balanced tree lookups, and heap operations all work this way.

Interactive 3D Visualization

Heap (Priority Queue)
Insert: O(log n)Extract: O(log n)Space: O(n)
Drag to orbit - Scroll to zoom

Python Implementation

example.py
Loading...
Now try it yourself
1 challenge with test cases and AI feedback
Practice Now

Complexity Analysis

1481216n²nlog n1n (input size)
COMMON OPERATIONS
Array
Access:O(1)
Search:O(n)
Insert end:O(1)*
Insert mid:O(n)
Hash Map
Get/Set:O(1)*
Delete:O(1)*
Search value:O(n)
Iterate:O(n)
Linked List
Access:O(n)
Search:O(n)
Insert head:O(1)
Delete known:O(1)
Binary Search
Search:O(log n)
Insert:O(log n)
Balanced BST
Search:O(log n)
Insert:O(log n)
Delete:O(log n)
Heap
Peek min/max:O(1)
Push:O(log n)
Pop:O(log n)
Heapify:O(n)
Graph (BFS/DFS)
Traversal:O(V+E)
Dijkstra (heap):O((V+E) log V)
Merge / Quick Sort
Sort:O(n log n)
Space (merge):O(n)
Space (quick):O(log n)

* amortized average case

READY TO TEST YOURSELF?

Put Heaps / Priority Queues into practice

The best way to lock in what you've learned is to write code. Solve real interview-style problems right now.

Next: Tries
Heaps / Priority Queues
Next: Tries