Min-Heap Implementation and Use Cases

What is a Min-Heap?

A min-heap is a complete binary tree where every parent node has a value less than or equal to its children. The smallest element always sits at the root, giving us O(1) access to the minimum. Think of it like a tournament bracket played in reverse — the weakest player always floats to the top.

The beauty of a min-heap is that it maintains this ordering property while keeping the tree perfectly balanced (complete), which means we can represent it efficiently using a simple array. No pointers, no node objects — just an array where for any element at index i:

• Left child is at 2*i + 1
• Right child is at 2*i + 2
• Parent is at (i - 1) // 2

Array Representation

Consider this min-heap: the root is 1, its children are 3 and 2, and 3's children are 7 and 6, while 2's children are 5 and 4.

Core Operations

Insert (Bubble Up / Sift Up)

When you insert a new element, place it at the end of the array (next available leaf position), then "bubble it up" by repeatedly swapping with its parent until the heap property is restored.

Time complexity: O(log n) in the worst case (element bubbles all the way to the root), but O(1) on average for random insertions.

Extract-Min (Bubble Down / Sift Down)

This is the signature operation. We remove the root (minimum element), move the last element to the root position, then "bubble it down" by swapping with the smaller child until order is restored.

Time complexity: O(log n) — at most the height of the tree.

Decrease-Key

This operation reduces the value of a key at a given index, then bubbles it up since it might now be smaller than its parent. This is crucial for Dijkstra's algorithm.

Time complexity: O(log n).

Peek (Get Minimum)

Simply return self.heap[0]. O(1) time.

Building a Heap: O(n) Magic

You might think building a heap from n elements takes O(n log n) — insert each one. But there is a smarter approach called heapify. Start from the last non-leaf node and bubble down each one:

Why is this O(n)? Most nodes are near the bottom and barely need to move. Mathematically, the sum of (height of node × number of nodes at that height) converges to O(n). This is a classic result that surprises many students.

Connection to Dijkstra's Algorithm

Dijkstra's shortest path algorithm needs to repeatedly find the unvisited vertex with the smallest tentative distance. A min-heap serves as the priority queue that makes this efficient:

Without a heap, Dijkstra runs in O(V²). With a binary min-heap, it runs in O((V + E) log V). With a Fibonacci heap (which supports O(1) amortized decrease-key), it achieves O(V log V + E), though Fibonacci heaps are rarely used in practice due to high constant factors.

Python's heapq Module

Python's standard library provides heapq, which implements a min-heap on top of a regular list:

Note: Python only provides min-heap. For a max-heap, negate values: push -val and negate again when popping.

Complexity Summary

When to Use a Min-Heap

• Priority scheduling: OS task schedulers pick the highest-priority (lowest value) task next
• Dijkstra/Prim's: Need repeated minimum extraction from a dynamic set
• Merge K sorted lists: Always pick the smallest head among K lists
• Streaming median: Combined with a max-heap for the two-heap technique
• Huffman coding: Repeatedly merge the two least-frequent symbols

Common Pitfall

Students often confuse "heap" with "heap memory." They are completely unrelated. The heap data structure is about tree-based ordering; heap memory is a region for dynamic allocation. Also remember: a min-heap does NOT give you sorted order for free — only the minimum is guaranteed at the root. The rest of the array is only partially ordered.