Skip to content

Instantly share code, notes, and snippets.

@leebyron
Last active January 28, 2019 05:08
Show Gist options
  • Save leebyron/0a7a2aaa51dcb5b02bc0b9a40188af79 to your computer and use it in GitHub Desktop.
Save leebyron/0a7a2aaa51dcb5b02bc0b9a40188af79 to your computer and use it in GitHub Desktop.
PriorityQueue.js uses a binary heap to ensure the highest priority item is always available to dequeue, and sorts on enqueue. A dynamically resizing Array can be used to model the binary heap, for a simpler and more efficient implementation.
/**
* For compare function return:
* - Less than zero: item1 has higher priority than item2.
* - Zero: same.
* - Greater than zero: item1 has lower priority than item2.
*/
export type CompareFunction<T> = (item1: T, item2: T) => number;
export class PriorityQueue<T> {
_items: Array<T>;
_compare: CompareFunction<T>;
constructor(compare: CompareFunction<T>): void {
this._items = [];
this._compare = compare;
}
enqueue(item: T): void {
let child = this._items.push(item) - 1;
// Satisfy heap by recursively comparing to parent node.
while (child !== 0) {
const parent = (child - 1) >>> 1;
if (this._priority(parent, child) === parent) {
break;
}
this._swap(parent, child);
child = parent;
}
}
dequeue(): ?T {
const length = this._items.length;
if (length !== 0) {
this._swap(0, length - 1);
const result = this._items.pop();
// Satisfy heap by recursively comparing to child nodes.
let parent = 0;
while (true) {
const child = (parent << 1) + 1;
const high = this._priority(this._priority(parent, child), child + 1);
if (high === parent) {
break;
}
this._swap(parent, high);
parent = high;
}
return result;
}
}
_priority(parent: number, child: number): number {
return child < this._items.length &&
this._compare(this._items[parent], this._items[child]) > 0
? child
: parent;
}
_swap(parent: number, child: number): void {
const temp = this._items[parent];
this._items[parent] = this._items[child];
this._items[child] = temp;
}
}
@leebyron
Copy link
Author

leebyron commented Apr 4, 2018

Includes type definitions which work in both TypeScript and Flow.

@leebyron
Copy link
Author

leebyron commented Apr 5, 2018

By the way, two common methods Queues often have are length and peek. The additions of which become trivial by using an Array as a binary heap:

get length(): number {
  return this._items.length;
}

peek(): ?T {
  return this._items[0];
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment