Min-Heap

Data Structures

avgO(log n)worstO(log n)spaceO(n)

A min-heap of 6; the minimum 8 sits at the root

1 / 47

Code

class MinHeap {  private a: number[] = [];  insert(value: number) {    this.a.push(value);    let i = this.a.length - 1;    while (i > 0) {      const p = (i - 1) >> 1;      if (this.a[p] <= this.a[i]) break;      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];      i = p;    }  }  extractMin() {    const min = this.a[0];    const last = this.a.pop()!;    if (this.a.length > 0) {      this.a[0] = last;      let i = 0;      while (true) {        const l = 2 * i + 1, r = l + 1;        let s = i;        if (l < this.a.length && this.a[l] < this.a[s]) s = l;        if (r < this.a.length && this.a[r] < this.a[s]) s = r;        if (s === i) break;        [this.a[i], this.a[s]] = [this.a[s], this.a[i]];        i = s;      }    }    return min;  }}

structure MinHeap  A ← empty array    ▷ A[i]'s children are A[2i+1] and A[2i+2]  procedure insert(value)    append value to A    i ← last index    while i > 0 do    ▷ sift up      p ← ⌊(i − 1) / 2⌋      if A[p] ≤ A[i] then stop      swap A[p] and A[i]      i ← p    end while  end procedure  procedure extractMin()    min ← A[0]    last ← remove the last element    if A is not empty then      A[0] ← last      i ← 0      loop    ▷ sift down        l ← 2i + 1; r ← 2i + 2        s ← i        if l exists and A[l] < A[s] then s ← l        if r exists and A[r] < A[s] then s ← r        if s = i then stop        swap A[i] and A[s]        i ← s      end loop    end if    return min  end procedureend structure

Variables

size=6

Counters

comparisons: 0
swaps: 0

Starting contents6 values

Operations6 / 40

1. insert(3)
2. insert(12)
3. pop()
4. insert(1)
5. pop()
6. pop()

How it works

A complete binary tree stored in an array where every parent is ≤ its children, so the minimum is always at the root. Insert sifts the new value up; extract-min moves the last value to the root and sifts it down. Most priority queues, including the one inside Dijkstra's algorithm, are built this way.

Complexity

Best: O(1)
Average: O(log n)
Worst: O(log n)
Space: O(n)

Min-Heap

How it works

Complexity

Search algorithms