Here is MaxHeap implementation in pure JavaScript:
/**
* We initialize index 0 because, calculations for finding
* children of a node and the parent of a node is easier
* parent = [ k/2 ], children: [ k*2, k*2+1 ]
*/
class Heap {
constructor() {
this.queue = [0];
};
/**
* Bottom-up reheapify (swim) : If the heap order is violated because a node's key
* becomes larger than that node's parents key, then we can make progress
* toward fixing the violation by exchanging the node with its parent
*
* @param {Number} k
*/
swim(k) {
while ( k>1 && this.less(k, Heap.flr(k/2)) ) {
this.exch(k, Heap.flr(k/2) ) ;
k = Heap.flr(k/2);
}
};
/**
* Top-down heapify (sink) : If the heap order is violated because a node's key becomes
* smaller than one or both of that node's children's keys, then we can make progress
* toward fixing the violation by exchanging the node with the larger of its two children.
*
* @param {Number} k
*/
sink(k) {
while ( 2*k <= this.n() ) {
const c1 = 2*k;
const c2 = 2*k + 1;
const j = this.more(c1,c2)?c2:c1;
if (this.more(k, j) ) {
this.exch(k, j);
} else {
break;
}
k = j;
}
};
/**
*
* @param {Number} i
* @param {Number} j
*/
less(i,j) {
return this.queue[i]>this.queue[j];
};
/**
*
* @param {Number} i
* @param {Number} j
*/
more(i,j) {
return this.queue[i]<this.queue[j];
};
/**
*
* @param {Number} i
* @param {Number} j
*/
exch(i, j) {
const tmp = this.queue[i];
this.queue[i] = this.queue[j];
this.queue[j] = tmp;
};
/**
* Inserts element into the internal queue
* @param {Number} k
*/
insert(k) {
this.queue.push(k);
this.swim(this.n());
};
/**
* Returns max element in the internal queue
*/
max() {
if (!this.isEmpty() ) {
return this.queue[1];
}
return false;
};
/**
* Deletes and returns max element from the internal queue
*/
delMax() {
if (!this.isEmpty()) {
const mx = this.queue[1];
this.queue[1] = this.queue.pop();
if (!this.isEmpty()) {
this.sink(1);
}
return mx;
};
return false;
};
/**
* Checks for emptyness (here we consider the queue empty if the length of the queue is 1)
*/
isEmpty() {
return this.queue.length === 1;
};
/**
* Returns last element index in the internal queue
*/
n() {
return this.queue.length-1;
};
/**
* in JS dividing odd number by even number gives fraction not integer,
* we need to get rid of this part
* @param {Number} i
*/
static flr(i) {
return Math.floor(i);
}
}
Is the implementation correct? What are the shortcomings that can be fixed?
