Heap.js

// By Steve Hanov (2014)
// Released to public domain
//
// Minimum element is always on top.
// You can pass in an optional lessThan(a, b) function to the constructor.
// You may use .length to retrieve the length. Try not to set it though.

function Heap()
{
    if (arguments.length) {
        this.lessThan = arguments[0];
    } else {
        this.lessThan = function(a, b) {
            return a < b;
        };
    }
    this.length = 0;
    this.A = [];
}

Heap.prototype = {

    push: function(item) {
        var A = this.A;
        A.push(item);
        var i = A.length-1;
        while(i > 0 && !this.lessThan(A[i/2|0], A[i])) {
            var temp = A[i/2|0];
            A[i/2|0] = A[i];
            A[i] = temp;
            i = i/2|0;
        }

        this.length += 1;
    },

    pop: function() {
        var A = this.A;
        if (A.length === 0) {
            return;
        }

        var max = A[0];
        A[0] = A[A.length-1];
        this._heapify(0);
        A.length -= 1;
        this.length -= 1;
        return max;
    },

    _heapify: function(i) {
        i += 1;
        var l = 2 * i;
        var r = 2 * i + 1;
        var A = this.A;
        var largest;
        if (l <= A.length && this.lessThan(A[l-1], A[i-1])) {
            largest = l;
        } else {
            largest = i;
        }

        if (r <= A.length && this.lessThan(A[r-1], A[largest-1])) {
            largest = r;
        }

        if (largest !== i) {
            var temp = A[i-1];
            A[i-1] = A[largest-1];
            A[largest-1] = temp;
            this._heapify(largest-1);
        }
    }
};

Heap.test = function()
{
    var heap = new Heap();
    heap.push(3);
    heap.push(2);
    heap.push(4);
    heap.push(1);
    heap.push(5);

    if (heap.pop() !== 1) {
        throw "Failed";
    }

    if (heap.pop() !== 2) {
        throw "Failed";

    }

    if (heap.pop() !== 3) {

        throw "Failed";
    }

    if (heap.pop() !== 4) {
        throw "Failed";

    }

    if (heap.pop() !== 5) {
        throw "Failed";
    }
};

Heap.ts

/** 
 By Steve Hanov. Released to the public domain 2018.

This version is in typescript and also includes the ability to pop() from an arbitrary location in the heap.
*/

export class Heap<T> {
    
    public length = 0;
    private A = new Array<T>();

    constructor(private lessThan: (a:T,b:T) => boolean = null) {
        if (this.lessThan == null) {
            this.lessThan = function(a:T, b:T):boolean {
                return a < b;
            };
        }        
    }

    toSortedArray() {
        let a = this.A.concat();
        a.sort( (a, b) => {
            return this.lessThan(a, b) ? -1 : 1;
        });
        return a;
    }

    toArray() {
        return this.A.concat();
    }

    heapify() {
        for(let i = this.A.length - 1; i >= 0; i--) {
            this.pushDown(i);
        }
    }

    clear() {
        this.length = 0;
        this.A.length = 0;
    }

    push(item:T) {
        this.pushUp(this.A.length, item);
        this.length += 1;
    }

    top():T {
        if (this.length) {
            return this.A[0];
        } else {
            return null;
        }
    }

    pop(i:number = 0) {
        var A = this.A;
        if (A.length <= i) {
            return;
        }

        var max = A[i];
        if (i === 0) {
            A[i] = A[A.length-1];
        } else {
            i = this.pushUp(i, A[A.length-1]);
        }

        A.length -= 1;
        this.length -= 1;


        this.pushDown(i);


        return max;
    }

    get(i:number):T {
        return this.A[i];
    }

    private pushUp(i:number, item:T) {
        let A = this.A;
        i += 1;

        while(i > 1 && !this.lessThan(A[(i/2|0)-1], item)) {
            A[i-1] = A[(i/2|0)-1];
            i = i/2|0;
        }
        A[i-1] = item;
        return i-1;
    }

    private pushDown(i:number) {
        let A = this.A;
        i += 1;
        while(true) {
            let l = 2 * i;
            let r = 2 * i + 1;
            let smallest;
            if (l <= A.length && this.lessThan(A[l-1], A[i-1])) {
                smallest = l;
            } else {
                smallest = i;
            }

            if (r <= A.length && this.lessThan(A[r-1], A[smallest-1])) {
                smallest = r;
            }

            if (smallest === i) {
                break;
            }

            let temp = A[i-1];
            A[i-1] = A[smallest-1];
            A[smallest-1] = temp;
            i = smallest;
        }
    }
    
    static test()
    {
        var heap = new Heap<number>();
        heap.push(3);
        heap.push(2);
        heap.push(4);
        heap.push(1);
        heap.push(5);

        if (heap.pop() !== 1) {
            throw "Failed";
        }

        if (heap.pop() !== 2) {
            throw "Failed";

        }

        if (heap.pop() !== 3) {

            throw "Failed";
        }

        if (heap.pop() !== 4) {
            throw "Failed";

        }

        if (heap.pop() !== 5) {
            throw "Failed";
        }

        function CheckHeap(heap) {
            let a = 0;
            while(heap.length) {
                let b = heap.pop();
                if (a > b) {
                    console.log("Heap error!");
                    console.log(heap.A);
                    throw "Heap error";
                }
                a = b;
            }
        }

        for (let j = 0; j < 1; j++) {

            for(let i = 0; i < 100; i++) {
                heap.push(Math.random());
            }

            for(let i = 0; i < 20; i++) {
                let index = Math.floor(Math.random() * heap.length);
                heap.pop(index);
            }
            CheckHeap(heap);

            for(let i = 0; i < 100; i++) {
                heap.push(Math.random());
            }

            Shuffle(heap.A);
            heap.heapify();
            CheckHeap(heap);
        }

        console.log("Heap test passed.");
    }
}