HeapsData structureaka min priority queue, minimum heap

Min-Heap

A complete binary tree stored in an array where every parent is ≤ its children, so the minimum is always at the root.

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

Progress

Definition

A min-heap is a Binary Heap with the ordering rule parent ≤ child. The smallest element sits at index 0 and can be read in O(1); inserting a value or removing the minimum costs O(log n) because only one root-to-leaf path is touched.

It is the standard backing store for a Priority Queue when "highest priority" means "smallest key": Dijkstra's Algorithm pops the closest unvisited vertex, Prim's Algorithm pops the cheapest crossing edge, k-way merge pops the smallest head, and event simulators pop the earliest timestamp.

A heap is not a sorted structure. It only guarantees the root is minimal; siblings are in no particular order and a level-order read of the array is not sorted. Searching for an arbitrary value is O(n).

priority queuecomplete binary treearray-backedO(log n)partial order

Intuition

A mental model before the formal terms.

Picture a tournament bracket for "who is smallest". Each match is a parent node holding the winner (smaller) of its two children. The overall champion is at the top. When the champion is removed, you only need to re-run the matches along one path from the vacated spot to a leaf — about log₂ n matches — not the whole bracket.

Inserting a new player works in reverse: drop them at the bottom, and let them "bubble up" past any parent they beat until they lose a match.

How it works

Store the tree level by level in an array. For index i: parent is (i - 1) / 2, children are 2i + 1 and 2i + 2. No pointers needed because the tree is complete (every level full except possibly the last, filled left to right).
Insert(x): append x at the end (keeps the tree complete), then sift up: while x is smaller than its parent, swap them.
Extract-min: save a[0], move the last element to index 0, shrink the size, then sift down: repeatedly swap with the smaller child while that child is smaller.
Peek: return a[0].
Heapify(array) in O(n): sift down every internal node from index n/2 - 1 down to 0. Most nodes are near the leaves and sift only a step or two, so total work is bounded by 2n.
Decrease-key(i, newVal): set a[i] = newVal (smaller than before) and sift up from i. Requires knowing the index, so practical implementations either keep a position map or use lazy deletion (push a new entry, skip stale ones on pop).

Why it works

The heap invariant is local (each parent ≤ its children) but implies a global fact: by induction along any root-to-leaf path, the root is ≤ every node in the tree.

Sift-up only ever swaps a node with a larger parent, so every subtree not on the path stays valid, and the node moving up is ≤ the subtree it now roots because it was ≤ the old parent which was ≤ everything below.

Sift-down swaps with the *smaller* child, guaranteeing the new parent is ≤ both children. The path length is the tree height, ⌊log₂ n⌋, which bounds every operation.

Operations

Operation	Description	Cost
peek / top	Return the minimum element at index 0.	O(1)
push / insert	Append at the end and sift up until the parent is smaller.	O(log n)
pop / extract-min	Swap root with last element, remove it, sift the new root down.	O(log n)
heapify	Build a heap from an arbitrary array by sifting down internal nodes right to left.	O(n)
decrease-key	Lower a key at a known index and sift it up.	O(log n)
delete(i)	Move the last element into index i, then sift up or down as needed.	O(log n)
search	No ordering across siblings; must scan the array.	O(n)

Recognition

How to tell a problem wants this.

The problem repeatedly asks for the smallest (or earliest, cheapest, closest) item from a changing set.
"Top k largest" — counterintuitively, keep a min-heap of size k; its root is the k-th largest and anything smaller than the root is discarded.
Merging k sorted streams, scheduling by earliest deadline, or any shortest-path / MST algorithm that greedily picks the minimum.
Constraints of n ≤ 10^5 with a need for repeated min-extraction rule out O(n) scans per step.

“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

1push(x):
2  a.append(x); i = len(a) - 1
3  while i > 0 and a[(i-1)/2] > a[i]: swap(i, (i-1)/2); i = (i-1)/2
4pop():
5  top = a[0]; a[0] = a.pop_last()
6  i = 0
7  loop: c = smaller child of i
8    if c exists and a[c] < a[i]: swap(i, c); i = c else break
9  return top

Implementation

1import heapq
2 
3 
4class MinHeap:
5    """Thin wrapper over heapq — Python's heap functions are min-heap already."""
6 
71 · Storage and construction
8    def __init__(self, items=None):
9        self._a = list(items) if items is not None else []
10        heapq.heapify(self._a)  # O(n) bottom-up heapify
11 
122 · Push
13    def push(self, x) -> None:
14        heapq.heappush(self._a, x)  # O(log n) sift-up
15 
163 · Pop (extract-min)
17    def pop(self):
18        return heapq.heappop(self._a)  # raises IndexError when empty
19 
20    def pushpop(self, x):
21        """Push then pop in one O(log n) sift — faster than push + pop."""
22        return heapq.heappushpop(self._a, x)
23 
244 · Peek and size
25    def peek(self):
26        return self._a[0]
27 
28    def __len__(self) -> int:
29        return len(self._a)
30 
31    def __bool__(self) -> bool:
32        return bool(self._a)

Walkthrough

heapq operates on a plain list in-place and is already a min-heap — no orientation fix needed.
heapify is O(n) bottom-up construction; the wrapper does it once in __init__.
heappush/heappop are the O(log n) sift operations, implemented in C.
heappushpop fuses push+pop into a single sift — useful for fixed-size top-k heaps.
peek is just self._a[0]; the heap invariant guarantees index 0 is the minimum.

Complexity (this implementation)

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

Language notes

heapq is a module of functions over a list, not a class — this wrapper only adds an object interface.
Tuples compare lexicographically, so (priority, tiebreak, payload) works; add an itertools.count() tiebreaker when payloads are not comparable.
For a max-heap, negate keys or use the undocumented heapq._heapify_max (do not, in interviews).
queue.PriorityQueue is the thread-safe wrapper around heapq — slower, only for concurrency.

Common mistakes in this language

Pushing (priority, obj) where two priorities tie and obj is not comparable — TypeError at pop time.
Treating the backing list as sorted (only a[0] is guaranteed minimal).
Calling heapq.heappush on a list that was never heapified.

Language differences that matter here

Heap orientation: Python heapq is min-heap by default; C++ std::priority_queue is MAX-heap by default (fix with std::greater); JS/TS have no built-in heap at all — you hand-roll or import one.
C++ pop() returns void (read top() first); Python heappop and the JS/TS pop return the removed element.
Bulk build: all four expose O(n) construction (heapify / iterator-range constructor / bottom-up loop) — always prefer it over n pushes.
Python heapq works on a bare list you also own; C++/JS/TS encapsulate the array, so accidental outside mutation is only possible in Python.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Minimum only (index 0).
Search	O(n)	O(n)
Insert	O(1)	O(log n)	Average sift-up depth is constant for random keys.
Delete	O(log n)	O(log n)	Arbitrary delete needs the index.
Update	O(log n)	O(log n)	Decrease-key: sift up from known index.
Peek	O(1)	O(1)
Extract-min	O(log n)	O(log n)
Decrease-key	O(log n)	O(log n)
Heapify	O(n)	O(n)
Space	O(n)

Advantages & disadvantages

Advantages

Contiguous array storage: no pointers, excellent cache behaviour, tiny constant factors.
O(n) bulk construction beats n individual inserts (O(n log n)).
O(1) access to the minimum with O(log n) updates — strictly better than a sorted array for a mutable set.
Built into every standard library: heapq, std::priority_queue, java.util.PriorityQueue, container/heap.

Disadvantages

No efficient search or arbitrary delete without an auxiliary index map.
Only the minimum is accessible; finding the second smallest or iterating in order requires popping.
Decrease-key needs an index map or lazy deletion, both of which add bookkeeping.
Not stable: equal keys come out in unspecified order unless you add a tiebreaker (e.g. an insertion counter).

Use cases

Dijkstra's Algorithm and Prim's Algorithm: pop the vertex/edge with minimum tentative cost.
Merge k sorted lists: heap of (value, listIndex) heads.
Top-k largest elements of a stream with a size-k min-heap.
Event-driven simulation and timers: pop the earliest scheduled event.
Huffman coding: repeatedly merge the two least frequent symbols.

Use it when

You need the minimum of a set that changes over time, interleaved with inserts.
Top-k largest of a stream with bounded memory (heap of size k).
Greedy algorithms that always take the cheapest available option (Dijkstra's Algorithm, Prim's Algorithm, Huffman Coding).
Merging many sorted sequences.

Avoid it when

You need both the min and the max frequently — use two heaps, a balanced BST, or a Monotonic Queue for sliding windows.
Frequent membership tests or lookups by key — a heap has no index; pair it with a Hash Map or use a Binary Search Tree.
The whole set must be sorted once — just sort; heap-based sorting is O(n log n) with worse constants than Merge Sort or Quick Sort.
Keys are small integers in a fixed range — a bucket/counting approach gives O(1) extraction.

Alternatives

Max-Heap Priority Queue Binary Search Tree Fibonacci Heap Monotonic Queue

Common mistakes

Treating the heap array as sorted — a[1] < a[2] is not guaranteed.
Using the language default without checking direction: Python heapq is a min-heap; C++ std::priority_queue is a max-heap by default.
Comparing tuples with non-comparable payloads in Python — add a unique counter as the second tuple element.
Sifting down toward the *larger* child, which breaks the invariant for the other child.
Forgetting to handle the case where the popped element was the last one (no sift needed).

Interview patterns

Kth largest element: min-heap of size k over the stream, answer is the root.
Merge k sorted lists: heap keyed on the current head of each list.
Top-k frequent: count with a hash map, then a size-k min-heap keyed on frequency.
Two-heap median: max-heap for the lower half, min-heap for the upper half.
Task scheduling / meeting rooms: min-heap of end times to reuse the earliest free room.

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

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