ACAlgoGeeks

1function insert(val):
2  heap.push(val)
3  i = heap.length - 1
4  while i > 0 and heap[parent(i)] > heap[i]:
5    swap(heap[parent(i)], heap[i])
6    i = parent(i)
7 
8function extractMin():
9  min = heap[0]
10  heap[0] = heap.pop()
11  i = 0
12  while true:
13    smallest = min(i, left(i), right(i))
14    if smallest == i: break
15    swap(heap[i], heap[smallest])
16    i = smallest
17  return min

1class MinHeap {
2  private heap: number[] = [];
3 
4  insert(val: number) {
5    this.heap.push(val);
6    let i = this.heap.length - 1;
7    while (i > 0) {
8      const p = Math.floor((i - 1) / 2);
9      if (this.heap[p] <= this.heap[i]) break;
10      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
11      i = p;
12    }
13  }
14 
15  extractMin(): number {
16    const min = this.heap[0];
17    this.heap[0] = this.heap.pop()!;
18    let i = 0;
19    while (true) {
20      let s = i;
21      const l = 2*i+1, r = 2*i+2;
22      if (l < this.heap.length && this.heap[l] < this.heap[s]) s = l;
23      if (r < this.heap.length && this.heap[r] < this.heap[s]) s = r;
24      if (s === i) break;
25      [this.heap[i], this.heap[s]] = [this.heap[s], this.heap[i]];
26      i = s;
27    }
28    return min;
29  }
30}

About

A Min Heap is a complete binary tree where each node is smaller than or equal to its children. It supports O(log n) insert and extract-min operations. The tree is stored compactly in an array.

Step-by-step explanation

Step 1 — Array representation: The heap is stored in an array where the root is at index 0. For a node at index i, its left child is at 2*i+1 and right child at 2*i+2; its parent is at floor((i-1)/2). The tree is complete: all levels are full except possibly the last, filled left to right.

Step 2 — Insert (bubble up): Add the new element at the end of the array (next free position in the complete tree). Then "bubble up": while the element is smaller than its parent, swap it with the parent. Repeat until the heap property (parent <= children) is restored. This takes O(log n) steps.

Step 3 — Extract minimum: The minimum is at the root (index 0). Replace it with the last element in the array and reduce the size by one. Then "bubble down" (sift down): while the element is greater than the smaller of its two children, swap it with that child. Repeat until the heap property holds. O(log n) steps.

Step 4 — Use cases: Heaps are used for priority queues, heapsort, and algorithms like Dijkstra that repeatedly need the smallest element. Build heap from n elements can be done in O(n) by sifting down from the last non-leaf to the root.

What's happening

Min-Heap initialized (empty)

Time Complexity

O(log n) insert/extract

Space Complexity

O(n)

Output

Min-Heap initialized (empty)