Skip to content

Instantly share code, notes, and snippets.

@matthayter
Last active July 24, 2022 11:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save matthayter/d151e0d61575aa29dbf2e7a64299cd33 to your computer and use it in GitHub Desktop.
Save matthayter/d151e0d61575aa29dbf2e7a64299cd33 to your computer and use it in GitHub Desktop.
A (mediocre) heap implementation in Typescript
class MinHeap<T> {
// op: return true when a should be above b.
static fromMutableArr<T>(arr: T[], op: (a: T, b: T) => boolean) {
this.heapify(arr, op);
return new MinHeap<T>(arr, op);
}
static heapify<T>(arr: T[], op: (a: T, b: T) => boolean) {
let start = parent(arr.length - 1);
for (let i = start; i >= 0; i--) {
MinHeap.siftDown(arr, i, op);
}
// for (let i = start; i >= 0; i--) {
// if ((rightChild(i) < arr.length && arr[i] > arr[rightChild(i)]) ||
// arr[i] > arr[leftChild(i)]) {
// console.log("Failed to heapify");
// }
// }
}
static siftDown<T>(arr: T[], start: number, op: (a: T, b: T) => boolean) {
let root = start;
while (leftChild(root) < arr.length) {
const child = leftChild(root);
let swap = root;
if (!op(arr[root], arr[child])) swap = child;
if (child+1 < arr.length && !op(arr[swap], arr[child+1])) swap = child+1;
if (swap == root) return;
MinHeap.swap(arr, root, swap);
root = swap;
}
}
static swap<T>(arr: T[], a: number, b: number) {
[arr[a], arr[b]] = [arr[b], arr[a]];
}
constructor(public heap: T[], public op: (a: T, b: T) => boolean) {}
add(v: T) {
this.heap.unshift(v);
MinHeap.siftDown(this.heap, 0, this.op);
console.log("Add", v, "; heap is now", this.heap.toString());
}
popMin(): T {
if (this.heap.length == 0) throw new Error("Empty");
if (this.heap.length == 1) return this.heap.pop();
MinHeap.swap(this.heap, 0, this.heap.length-1);
const min = this.heap.pop();
MinHeap.siftDown(this.heap, 0, this.op);
console.log("pop", min, "; heap is now", this.heap.toString());
return min;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment