Heap

Problem¶

Implement a min heap: a tree-like data structure stored in an array such that every parent is inferior or equal to its children.

In a min heap, the smallest value is always at the root.

Key trick¶

Store the complete binary tree in an array and restore the heap invariant using sift-up after insertion and sift-down after removing the root, giving \(O(\log n)\) updates.

Trap¶

During sift-down, compare both children and swap with the smaller one; also handle empty heaps, single-element heaps, duplicates, and child-index bounds correctly.

Why is it interesting?¶

It turns a tree into a compact array structure while keeping minimum lookup at \(O(1)\) and insertion/removal at \(O(\log n)\).

Python solution¶

class MinHeap:
    def __init__(self):
        self.heap = []

    def peek(self):
        return self.heap[0]

    def push(self, x):
        self.heap.append(x)
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        heap = self.heap
        if not heap:
            raise IndexError("pop from empty heap")

        smallest = heap[0]
        last = heap.pop()

        if heap:
            heap[0] = last
            self._sift_down(0)

        return smallest

    def _sift_up(self, i):
        heap = self.heap
        while i:
            j = (i - 1) // 2
            if heap[i] >= heap[j]:
                break
            heap[i], heap[j] = heap[j], heap[i]
            i = j

    def _sift_down(self, i):
        heap = self.heap
        n = len(heap)
        while 2 * i + 1 < n:
            j = 2 * i + 1
            if j + 1 < n and heap[j + 1] < heap[j]:
                j += 1
            if heap[i] <= heap[j]:
                break
            heap[i], heap[j] = heap[j], heap[i]
            i = j

    def __len__(self):
        return len(self.heap)

Extra¶

Definition¶

A heap is a tree-like data structure usually stored in an array, with one key rule:

• Min-heap:
  • Every parent is <= its children.
  • So the smallest value is always at the root.
• Max-heap:
  • Every parent is >= its children.
  • So the largest value is always at the root.

Important:

• A heap is not sorted.
• It only guarantees that the top element is easy to access.
• That is why it is great when you repeatedly need:
  • the smallest element
  • the largest element
  • the top k elements

Why heaps are useful in practice¶

Heaps are useful when the problem is about a changing "best" element.

Typical uses:

• Priority queues
  • "Always process the most urgent task next"
• Top k problems
  • k largest
  • k smallest
• Scheduling
  • next job to run
  • earliest finishing event
• Graph algorithms
  • Dijkstra
  • Prim
• Streaming data
  • numbers arrive one by one, but you still want current top k

How a heap is stored¶

Usually in an array.

Example heap array:

[2, 5, 3, 8, 7, 6]

This means:

        2
      /   \
     5     3
    / \   /
   8   7 6

Index relationships:

• left child of i is 2*i + 1
• right child of i is 2*i + 2
• parent of i is (i - 1) // 2

That is why heaps are simple and efficient in arrays.

Time idea¶

If you sort everything:

• \(O(n \log n)\)

If you keep a heap of size k:

• each update costs about \(O(\log k)\)
• total is \(O(n \log k)\)

This is much better when k is small compared to n.