Skip to content

Instantly share code, notes, and snippets.

@okmttdhr
Last active March 9, 2022 00:50
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 okmttdhr/5d343aea986476c15677c2057dece2c9 to your computer and use it in GitHub Desktop.
Save okmttdhr/5d343aea986476c15677c2057dece2c9 to your computer and use it in GitHub Desktop.
PriorityQueue in TypeScript
const root = 0;
const parentIndex = i => Math.floor((i - 1) / 2);
const leftIndex = i => 2 * i + 1;
const rightIndex = i => leftIndex(i) + 1;
// With Bitwise Operations;
// const parentIndex = i => ((i + 1) >>> 1) - 1;
// const leftIndex = i => (i << 1) + 1;
// const rightIndex = i => (i + 1) << 1;
// Below is also valid;
// const parentIndex = i => ((i - 1) >>> 1)
// const leftIndex = i => (i << 1) + 1;
// const rightIndex = i => leftIndex(i) + 1;
class PriorityQueue {
_heap = [];
_comparator = (a, b) => a > b
constructor(comparator) {
this._comparator = comparator;
}
size() {
return this._heap.length;
}
peek() {
return this._heap[root];
}
enqueue(...values) {
values.forEach(value => {
this._heap.push(value);
this._siftUp();
});
return this.size();
}
dequeue() {
const poppedValue = this.peek();
this._swap(root, this.size() - 1);
this._heap.pop();
this._siftDown();
// With shift, unshift, pop
// const poppedValue = this.heap.shift();
// this.heap.unshift(this._heap[this.size() - 1]);
// this.heap.pop();
// this._siftDown();
return poppedValue;
}
_greater(i, j) {
return this._comparator(this._heap[i], this._heap[j]);
}
_swap(i, j) {
[this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]];
}
_siftUp() {
let node = this.size() - 1;
while (node > root && this._greater(node, parentIndex(node))) {
this._swap(node, parentIndex(node));
node = parentIndex(node);
}
}
_siftDown() {
let node = root;
while (
(leftIndex(node) < this.size() && this._greater(leftIndex(node), node)) ||
(rightIndex(node) < this.size() && this._greater(rightIndex(node), node))
) {
let maxChild = (rightIndex(node) < this.size() && this._greater(rightIndex(node), leftIndex(node)))
? rightIndex(node) : leftIndex(node);
this._swap(node, maxChild);
node = maxChild;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment