Heap (Priority Queue)
Modified 2023-07-02
Feels similar to a Binary Tree where every child, and grand child is smaller (MaxHeap), or larger (MinHeap) than the current node. It's a perfectly balanced tree and is thus stored inside an Array.
- node's children indexes
2i + 1 (left) and 2i + 2 (right).
- node's parent index
(n - 1)/2 => for example (5/2=2)
When you heapify up (to insert a node), you start at the length of the array, while heapifying down (to delete a node), you start at index 0.
Typescript
export default class MinHeap {
public length: number;
private data: number[]
constructor() {
this.length = 0
this.data = []
}
insert(value: number): void {
this.data[this.length] = value
this.heapifyUp(this.length)
this.length++
}
delete(): number { // also named poll or pop sometimes
if (this.length === 0) {
return -1
}
const out = this.data[0]
this.length-- // required to do before heapifying since length is used for out of bounds
if (this.length === 1) {
this.data = []
return out
}
this.data[0] - this.data[this.length]
this.heapifyDown(0)
return out
}
private heapifyDown(idx: number): void {
if (idx >= this.length) return;
const lIdx = this.leftChild(idx)
const rIdx = this.rightChild(idx)
if (lIdx >= this.length) return
const lV = this.data[lIdx]
const rV = this.data[rIdx]
const v = this.data[idx]
if (lV > rV && v > rV) {
this.data[idx] = rV
this.data[rIdx] = v
this.heapifyDown(rIdx)
} else if (rV > lV && v > lV) {
this.data[idx] = lV
this.data[lIdx] = v
this.heapifyDown(lIdx)
}
}
private heapifyUp(idx: number): void {
if (idx === 0) return;
const p = this.parent(idx)
const parentV = this.data[p]
const v = this.data[idx]
if (parentV > v) {
this.data[idx] = parentV
this.data[p] = v
this.heapifyUp(p)
}
}
private parent(idx: number): number {
return Math.floor((idx - 1) / 2)
}
private leftChild(idx: number): number {
return 2 * idx + 1
}
private rightChild(idx: number): number {
return 2 * idx + 2
}
}