Created
September 25, 2023 14:51
-
-
Save poetix/58799c6162d4cb98b8ff16aefa2eadd7 to your computer and use it in GitHub Desktop.
Heap and Priority Queue in Typescript
This file contains 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 Heap<T> { | |
selectMax: (l: T, r: T) => boolean; | |
data: T[]; | |
constructor(selectMax: (l: T, r: T) => boolean) { | |
this.selectMax = selectMax; | |
this.data = []; | |
} | |
length(): number { | |
return this.data.length; | |
} | |
peek(): T | undefined { | |
return this.data[0]; | |
} | |
add(item: T) { | |
this.data.push(item); | |
this.bubbleUp(item, this.data.length - 1); | |
} | |
bubbleUp(value: T, index: number) { | |
if (index == 0) return; | |
const parent = Math.floor((index + 1) / 2) - 1; | |
if (this.selectMax(this.data[index], this.data[parent])) { | |
this.data[index] = this.data[parent]; | |
this.data[parent] = value; | |
this.bubbleUp(value, parent); | |
} | |
} | |
remove(): T | undefined { | |
if (this.data.length == 0) return undefined; | |
if (this.data.length == 1) return this.data.shift(); | |
const result = this.data[0]; | |
this.data[0] = this.data.pop()!; | |
this.bubbleDown(this.data[0], 0); | |
return result; | |
} | |
bubbleDown(value: T, index: number) { | |
const childLeft = ((index + 1) * 2) - 1; | |
if (childLeft >= this.data.length) return; | |
const leftValue = this.data[childLeft]; | |
let selected: [T, number] = [this.data[childLeft], childLeft]; | |
const childRight = childLeft + 1; | |
if (childRight < this.data.length) { | |
const rightValue = this.data[childRight]; | |
if (this.selectMax(rightValue, leftValue)) { | |
selected = [rightValue, childRight]; | |
} | |
} | |
const [childValue, childIndex] = selected; | |
if (this.selectMax(childValue, value)) { | |
this.data[index] = childValue; | |
this.data[childIndex] = value; | |
this.bubbleDown(value, childIndex); | |
} | |
} | |
} | |
class PriorityQueue<I, T> { | |
heap: Heap<[I, T]> | |
constructor(selectMax: (left: I, right: I) => boolean) { | |
this.heap = new Heap<[I, T]>((left: [I, T], right: [I, T]) => selectMax(left[0], right[0])); | |
} | |
add(priority: I, item: T) { | |
this.heap.add([priority, item]); | |
} | |
peek() : T | undefined { | |
const peeked = this.heap.peek(); | |
if (peeked == undefined) return undefined; | |
return peeked[1]; | |
} | |
remove(): T | undefined { | |
const removed = this.heap.remove(); | |
if (removed == undefined) return undefined; | |
return removed[1]; | |
} | |
length(): number { | |
return this.heap.length(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment