Min Heap Construction

Tags

Min Heap Construction

Category

Heaps

Difficulty

Medium

Problem Statement

Implement a Min Heap class that supports the following operations:

  • buildHeap(array): Build a heap from an input array in place.
  • insert(value): Insert a value into the heap.
  • remove(): Remove and return the minimum value (the root).
  • siftUp(index): Move a node up to restore the heap property.
  • siftDown(index): Move a node down to restore the heap property.
  • peek(): Return the minimum value without removing it.

Intuition

A min heap is a complete binary tree where every parent node is less than or equal to its children. It is stored as a flat array where for index i, the left child is at 2i + 1, the right child at 2i + 2, and the parent at (i - 1) / 2 (integer division). The heap property is maintained through two key operations: siftUp (for insertions) and siftDown (for removals).

Approach

buildHeap

Start from the last parent node (index (n - 2) / 2) and sift down each node going backward to index 0. This bottom-up approach is O(n), faster than inserting elements one by one (which would be O(n log n)).

insert

Append the new value to the end of the array, then sift it up to its correct position.

remove

Swap the root (minimum) with the last element, remove the last element, then sift the new root down to its correct position.

siftUp

Compare the node with its parent. If the node is smaller, swap them and continue upward until the heap property is restored or the root is reached.

siftDown

Compare the node with its children. Swap with the smaller child if that child is smaller than the node. Continue downward until the heap property is restored or a leaf is reached.

Pseudocode

class MinHeap:
    heap = []

    function buildHeap(array):
        heap = array
        lastParent = (length(heap) - 2) / 2
        for i from lastParent down to 0:
            siftDown(i)

    function insert(value):
        heap.append(value)
        siftUp(length(heap) - 1)

    function remove():
        swap(heap[0], heap[length(heap) - 1])
        minValue = heap.pop()
        siftDown(0)
        return minValue

    function siftUp(index):
        parentIndex = (index - 1) / 2
        while index > 0 and heap[index] < heap[parentIndex]:
            swap(heap[index], heap[parentIndex])
            index = parentIndex
            parentIndex = (index - 1) / 2

    function siftDown(index):
        endIndex = length(heap) - 1
        leftChild = 2 * index + 1
        while leftChild <= endIndex:
            rightChild = 2 * index + 2 if 2 * index + 2 <= endIndex else -1
            if rightChild != -1 and heap[rightChild] < heap[leftChild]:
                smallerChild = rightChild
            else:
                smallerChild = leftChild
            if heap[smallerChild] < heap[index]:
                swap(heap[smallerChild], heap[index])
                index = smallerChild
                leftChild = 2 * index + 1
            else:
                break

    function peek():
        return heap[0]

Time & Space Complexity

  • buildHeap: O(n) time — the bottom-up sift-down approach is mathematically proven to be linear.
  • insert: O(log n) time — siftUp traverses at most the height of the tree.
  • remove: O(log n) time — siftDown traverses at most the height of the tree.
  • siftUp / siftDown: O(log n) time.
  • peek: O(1) time.
  • Space: O(1) additional space for all operations (the heap is stored in the input array).

Key Insights

  • The array-based representation avoids the overhead of node pointers. Parent and child indices are computed with simple arithmetic.
  • Building a heap bottom-up with siftDown is O(n) because most nodes are near the bottom and require little sifting. Building top-down with siftUp would be O(n log n).
  • Swapping the root with the last element before removal is key — it maintains the complete binary tree structure.
  • siftDown must always swap with the smaller child to maintain the min heap property.

System Design Application

The min-heap (priority queue) is the core extraction mechanism in dijkstras-algorithm. Dijkstra's shortest-path algorithm uses a min-heap to efficiently extract the vertex with the smallest tentative distance in O(log V) time. Without a heap, extracting the minimum would require O(V) per iteration, degrading the algorithm from O((V + E) log V) to O(V^2).

The min-heap also underpins the priority queue tier in Web-Crawler-Design. A distributed web crawler uses priority queues to rank URLs by importance score (PageRank estimate, freshness signal, domain authority) so that the crawl budget is spent on high-value pages first.

Edge Cases

  • Building a heap from an empty array.
  • Removing from a single-element heap.
  • Inserting into an empty heap.
  • All elements are identical.
  • Array is already a valid heap — buildHeap still works correctly (no swaps needed).

Linked mentions