Last active
July 24, 2022 11:56
-
-
Save matthayter/d151e0d61575aa29dbf2e7a64299cd33 to your computer and use it in GitHub Desktop.
A (mediocre) heap implementation in Typescript
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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