priority-queue.ts

function swap<K, V>(indexA: number, indexB: number): void {
    const k: K = this.keys[indexA];
    const v: V = this.vals[indexA];
    this.keys[indexA] = this.keys[indexB];
    this.vals[indexA] = this.vals[indexB];
    this.keys[indexB] = k;
    this.vals[indexB] = v;
}

abstract class PriorityQueue<K, V> {
    // The backing store for the queue is a pair of key and value arrays, which
    // implicitly implement a binary tree: starting with the root node defined
    // at "head" index i=1, each node's children are indexed at 2*i and 2*i+1.
    keys: Array<K> = [undefined];
    vals: Array<V> = [undefined];
    length: number = 0;

    // The ordering operation over <K>. Returns {-1, 0, 1}. This alone defines
    // the distinction between concrete subclasses MinQueue and MaxQueue.
    abstract compare(a: K, b: K): number;
    
    enqueue (key: K, val: V): number {
        // Append the key–value pair onto the tail end of the backing arrays,
        // then bubble pairs toward the root (head) whenever a child's key is
        // "better" compared to the key of its parent.
        this.keys.push(key);
        this.vals.push(val);
        this.length += 1;

        let index = this.length;
        while (index > 1) {
            const parentIndex = index >> 1;
            const parentKey = this.keys[parentIndex];

            if (this.compare(key, parentKey) > 0) break;

            swap.call(this, index, parentIndex);
            index = parentIndex;
        }

        return this.length;
    }

    dequeue(): V {
        const bound: number = this.length;
        if (bound < 1) return;

        // Pop the tail pair; if this was the only pair in the queue, return its
        // value immediately.
        this.length -= 1;
        const poppedKey: K = this.keys.pop();
        const poppedVal: V = this.vals.pop();
        if (bound < 2) return poppedVal;

        // Otherwise, take the value to be dequeued from the root of the tree,
        // then replace the vacant root with the popped tail pair.
        const dequeuedValue: V = this.vals[1];
        this.keys[1] = poppedKey;
        this.vals[1] = poppedVal;
        let index: number = 1;
        
        // Descend the tree: swap parent–child pairs as necessary to ensure
        // that the key of each parent is always equal-or-better compared to
        // both of its children's keys.
        for (;;) {
            let bestIndex: number = index;
            let bestKey: K = this.keys[bestIndex];

            const leftIndex: number = index << 1;
            if (leftIndex > bound) break;
            const leftKey: K = this.keys[leftIndex];
            if (this.compare(bestKey, leftKey) > 0) {
                bestIndex = leftIndex;
                bestKey = leftKey;
            }

            const rightIndex: number = leftIndex + 1;
            if (rightIndex > bound) break;
            const rightKey: K = this.keys[rightIndex];
            if (this.compare(bestKey, rightKey) > 0) {
                bestIndex = rightIndex;
            }

            if (bestIndex === index) {
                break;
            } else {
                swap.call(this, index, bestIndex);
                index = bestIndex;
                continue;
            }
        }

        return dequeuedValue;
    }
}

export class MinQueue<K,V> extends PriorityQueue<K,V> {
    compare(a:K, b:K): number {
        return a < b ? -1 : a > b ? 1 : 0;
    }
}

export class MaxQueue<K,V> extends PriorityQueue<K,V> {
    compare(a:K, b:K): number {
        return a < b ? 1 : a > b ? -1 : 0;
    }
}

function example () {
    const q = new MaxQueue<number, string>();
    q.enqueue(10, 'foo');
    q.enqueue(3, 'bar');
    q.enqueue(5, 'baz');
    q.enqueue(1, 'qux');
    q.enqueue(20, 'fat');
    console.log(q);
}