BinaryHeap Optimization

Coding Help
1

Hi all,

Just the other day I learnt from an article that binaryheap is a great way to sort through items. After implementing a basic version, I’ve noticed that it is significantly slower then the built-in array.prototype.find method. After binaryheaps inherently slower then just using an array? Or is my task not suited for it?

// Massive thanks to https://www.geeksforgeeks.org/binary-heap/
export default class BinaryHeap {
    public array: any[];
    constructor() {
        this.array = [];
    };

    public left(i: number): number {
        return i * 2 + 1;
    };

    public right(i: number): number {
        return i * 2 + 2;
    };

    public getParent(i: number): number {
        return Math.floor((i - 1) / 2);
    };

    public getMin(): any {
        return this.array[0];
    };

    public insert(task: { priority: number, data: any }): void {
        this.array.push(task);

        let i = this.array.length - 1;
        while (i > 0 && this.array[this.getParent(i)].priority > this.array[i].priority) {
            let parent = this.getParent(i);
            [this.array[i], this.array[parent]] = [this.array[parent], this.array[i]];
            
            i = parent;
        };
    };

    public decreaseKey(i: number, val: any): void {
        this.array[i] = val;

        while (i != 0 && this.array[this.getParent(i)].priority > this.array[i].priority) {
            let parent = this.getParent(i);
            [this.array[i], this.array[parent]] = [this.array[parent], this.array[i]];
            
            i = parent;
        };
    };

    // we need for removing min of heap
    public extractMin(): any {
        if (this.array.length == 1) {
            return this.array.pop();
        }
         
        // store the minimum value, and remove it from heap 
        let res = this.array[0];
        this.array[0] = this.array[this.array.length - 1];
        this.array.pop();
        this.MinHeapify(0);
        return res;
    };

    public extractMax(): any {
        var i = this.array.length;
        //reverse minHeap syst to maxHeap
        while(i) {
            this.array[i - 1].priority = -this.array[i - 1].priority;

            i--;
        };

        console.warn(this.extractMin());
        var elem: any = this.extractMin(); //cus we just reversed it, the first elem has the highest priority instead

        //now to revert back to minHeap
        while(i) {
            this.array[i - 1].priority = -this.array[i - 1].priority;

            i--;
        };

        return elem;
    };

    public deleteKey(i: number): void {
        this.decreaseKey(i, this.array[0] - 1);
        this.extractMin();
    };

    public MinHeapify(i: number): void {
        let arr = this.array;
        let n = arr.length;
        let smallest = i;
        let l = this.left(i);
        let r = this.right(i);
    
        while (l < n) {
            if (arr[l].priority < arr[smallest].priority) {
                smallest = l;
            }
    
            if (r < n && arr[r].priority < arr[smallest].priority) {
                smallest = r;
            }
    
            if (smallest !== i) {
                [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
                i = smallest;
                l = this.left(i);
                r = this.right(i);
            } else {
                break;
            }
        }
    }    
};

var heap = new BinaryHeap();
for(let i = 0; i < 50000; i++) {
    heap.insert({priority: i, data: null});    
}

var startTime = performance.now();
var result = heap.array.find(a => a.priority == 0);
var endTime = performance.now();
console.log("Array find took " + (endTime - startTime) + "ms");

startTime = performance.now();
heap.insert({priority: 0, data: null});
var min = heap.extractMin();
endTime = performance.now();
console.log("Heap extractMin took " + (endTime - startTime) + "ms");

console.log("ok")

Any advice would be appreciated!

2

are you testing this with it already sorted and with prior knowledge of what priority you want, so that array .find gets it on the first try?

3

Yeah, I know what priority im looking for. Not sure about it being sorted though.

4

the other thing is your array version doesn’t remove the one it finds