# BinaryHeap Optimization

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 {

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")
``````

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?