Min-Heap

heappriority-queuecomplete-tree

Press play to start

1class MinHeap {
private heap: number[] = []
insert(val: number): void {
  this.heap.push(val)
  this.bubbleUp(this.heap.length - 1)
}
private bubbleUp(i: number): void {
  const p = Math.floor((i - 1) / 2)
  if (i > 0 && this.heap[i] < this.heap[p]) {
    [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]]
    this.bubbleUp(p)
  }
}
extractMin(): number | undefined {
  if (!this.heap.length) return undefined
  const min = this.heap[0]
  this.heap[0] = this.heap.pop()!
  this.heapifyDown(0)
  return min
}
21}

Step 1/0

Complexity

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

Description

A complete binary tree where every parent node is smaller than its children. The root is always the minimum element.

When to use

Priority queues, Dijkstra's algorithm, heap sort, scheduling systems. O(log n) insert and O(1) min access.