As part of my study on fundamentals, I have implemented the following code in JavaScript for a MinHeap data structure.
Please have a look and I look forward to your feedback for any improvements.
const swap = require('../swap');
function Heap(){
this.heap = [];
}
Heap.prototype.getParent = function(index){
return (index-1)/2;
}
Heap.prototype.getLeft = function(index){
return (2*index)+1;
}
Heap.prototype.getRight = function(index){
return (2*index)+2;
}
//inserts a new value to the min-heap
Heap.prototype.insert = function(value){
this.heap.push(value);
this.heapifyUp(this.heap.length-1);
return;
}
//deletes any node at given index
Heap.prototype.delete = function(index){
if(index === 0){
this.heap[0] = this.heap[this.heap.length-1];
this.heap.splice(this.heap.length-1, 1);
this.heapifyDown(0);
return;
}
this.heap[index] = this.heap[this.heap.length-1];
this.heap.splice(this.heap.length-1, 1);
var parent = this.getParent(index);
(this.heap[index]<this.heap[parent])? this.heapifyUp(index) : this.heapifyDown(index);
return;
}
//extracts min value and recalibrates minheap
Heap.prototype.extractMin = function(){
var temp = this.heap[0];
swap(this.heap, 0, (this.heap.length-1));
this.heap.slice((this.heap.length-1), 1);
this.heapifyDown(0);
return temp;
}
//decreases the value of node at given index by given value
Heap.prototype.decrease = function(index, value){
if((this.heap[index]-value)<0) return false;
this.heap[index] = this.heap[index]-value;
(index === 0) ? this.heapifyDown(0) : this.heapifyUp(index);
return;
}
Heap.prototype.heapifyUp = function(index){
var parent = this.getParent(index);
while(parent>=0 && this.heap[parent]>this.heap[index]){
swap(this.heap, parent, index);
index = parent;
parent = this.getParent(index);
}
}
Heap.prototype.heapifyDown = function(index){
var left = this.getLeft(index);
var right = this.getRight(index);
while(this.heap[index]>this.heap[left] || this.heap[index]>this.heap[right]){
if(this.heap[index]>this.heap[left]){
swap(this.heap, left, index);
index = left;
left = this.getLeft(index);
}
if(this.heap[index]>this.heap[right]){
swap(this.heap, right, index);
index = right;
right = this.getLeft(index);
}
}
}
delete(0): duplicates the item that is last in the array. You're missing thespliceto shorten the array. \$\endgroup\$decrease()it allows negative values, which cause the item to be increased in value, whic breaks up the heap property \$\endgroup\$