Skip to content

Instantly share code, notes, and snippets.

@axross
Last active August 18, 2019 04:47
Show Gist options
  • Save axross/78c8ac170b27b16c801e96916ce51c26 to your computer and use it in GitHub Desktop.
Save axross/78c8ac170b27b16c801e96916ce51c26 to your computer and use it in GitHub Desktop.
BinaryHeap
export default class BinaryHeap<T> {
constructor(orderComparator: OrderComparator<T>) {
this.orderComparator = orderComparator;
this.values = [];
}
private orderComparator: OrderComparator<T>;
private values: T[];
get length(): number {
return this.values.length;
}
peek(): T {
return this.values[0];
}
push(element: T): void {
this.values.push(element);
if (this.values.length >= 2) {
this.sinkDown(this.values.length - 1);
}
}
pop(): T {
if (this.values.length === 1) return this.values.pop()!;
const rootValue = this.peek();
this.values[0] = this.values.pop()!;
this.bubbleUp(0);
return rootValue;
}
private sinkDown(at: number): void {
const parent = Math.floor((at - 1) / 2);
if (
this.values[parent] !== undefined &&
this.orderComparator(this.values[at], this.values[parent]) > 0
) {
[this.values[at], this.values[parent]] = [
this.values[parent],
this.values[at]
];
this.sinkDown(parent);
}
}
private bubbleUp(at: number): void {
const left = at * 2 + 1;
const right = at * 2 + 2;
let largest = at;
if (
this.values[left] !== undefined &&
this.orderComparator(this.values[left], this.values[largest]) > 0
) {
largest = left;
}
if (
this.values[right] !== undefined &&
this.orderComparator(this.values[right], this.values[largest]) > 0
) {
largest = right;
}
if (largest !== at) {
[this.values[largest], this.values[at]] = [
this.values[at],
this.values[largest]
];
this.bubbleUp(largest);
}
}
static fromArray<T>(array: T[], orderComparator: OrderComparator<T>) {
const heap = new BinaryHeap<T>(orderComparator);
for (const element of array) {
heap.push(element);
}
return heap;
}
}
export type OrderComparator<T> = (a: T, b: T) => number;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment