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?

Bug

There's a bug in delMax:

const mx = this.queue[1];

this.queue[1] = this.queue.pop();

if (!this.isEmpty()) {   

    this.sink(1);

}

return mx;

What will happen when the heap has 1 element? The code will:

• Replace the first element with itself (the last element)


• It doesn't become empty

In other words, the last element cannot be deleted.

Avoid hacky solutions

This code happens to work, but it's hacky:

while ( 2*k <= this.n() ) {

    const c1 = 2*k; 

    const c2 = 2*k + 1;

    const j = this.more(c1,c2)?c2:c1;

What's wrong with it? When 2*k == this.n(), then c2 will point past the end of the queue, and more will compare queue[c1] with undefined, and always return false. The code works, but it would be better to not rely on numeric comparisons with undefined.

Look for generalization opportunities

It's a good idea to use a function to decide the ordering of elements, similar to what you did with less and more. This could open the opportunity to make the implementation work with arbitrary ordering.

The current implementation doesn't make it easy to pass in these functions to customize the behavior. It would be good to make that possible. And it would be even better to make it work with a single function, let's say less.

If you do that, then you should rename some methods, since max and delMax won't make sense for a min-heap ordering. You could rename these to peek and pop.

Hide implementation details

The class exposes many methods that are unnecessary for users:
swim, sink, less, more, exch, flr.
These are implementation details, and it would be best to hide them.

Drop the unnecessary trick

This trick:

/**

 * 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 ]

 */

Looks completely unnecessary... I don't see a reason whatsoever why the dummy first element helps. You can eliminate it, and the implementation will be simpler and clearer.

Dividing by 2

I'm not sure if this is recommended in JavaScript world,
but instead of Math.floor(x / 2),
x >> 1 feels cleaner.

Naming

Some method names could be improved:

• 
  exch -> swap
  


• 
  n -> size
  


• 
  insert -> add
  


• 
  flr -> floor, or instead of always calling it with flr(k / 2) you could name it childIndex and call it with k, letting it do the necessary math


• 
  flr uses parameter i. The name i is best in simple counting loops.

Protect state

There is a fundamental overriding principle in programing that if correctly followed ensures that your code will work. Encapsulate and protect the objects state so that you can trust its integrity.

You have exposed the objects state yet provide no means to ensure that the state is maintained in such a way that your code will run as expected.

The following actions are all possible and all make the whole object unusable. You have no systematic way to determine if the state of heap is safe to use. Yet you continue to try and perform actions on a broken state, and will eventually throw an unknown error

const heap = new Heap();

heap.insert("ABC"); 

heap.queue.pop(); 

heap.queue.push(-100); 

heap.queue.length = 0; 

heap.queue = "monkey bread";

heap.exch(0,1000);

A good object means that there is NO WAY to corrupt the state of the object. That if the state cannot be maintained a predefined known list of errors will be thrown.

techniques to protect state

• Use closure to hide data that is not relevant to the user of the object.


• Use setters to ensure only valid values can be set.


• Use getters and setters to create read only and write only values.


• Avoid the this token as it can be hijacked and means any code that uses the token can corrupt state.

Performance

After making state trustable you must address performance. I am often down voted for putting too much emphasis on performance, yet when a new app or framework comes out the reviews always make a point off performance. Poor performance is an app killer.

Performance starts at the very lowest level and is a mind set as much as a style. You should always be thinking, is there a faster way. You should also test and know what style are performant as in JavaScript it is not always evident.

• 
  

  Inline is faster than function calls. It is a balancing act between readability and performance, but when readability is marginal always go for the inline option.

  
  
  

  You have while(2*k <= this.n()) but could be while(2 * k < queue.length) Note queue should not be exposed.

  
  


• 
  

  Don't repeat calculations

  
  
  

  In swim you repeat the same calculation 3 times Heap.flr(k/2). It should be calculated once and stored as a variable. You do the same in other functions.

  
  


• 
  

  Don't pass known values

  
  
  

  You call sink and swim with argument k, which are always the same value (either 1 or queue.length - 1). There is no need to pass a known value.

  
  


• 
  

  Integers are faster than doubles

  
  
  

  Javascript does not have a definable integer type, but internally to take advantage of hardware performance Javascript Number can be a variety of types from uint32 to double. All bitwise operators use uint32 and will coerce doubles to uint32. Integers can be up to 2 times faster than doubles (more depending on the platform)

  
  
  

  You have Heap.flr(k/2) that will convert odd values of k to a double, then floor it in flr which converts it back to integer. Also you require two allocations to the call stack just to complete the operation. k >> 2 does the same thing, avoids the intermediate double and requires no use of the call stack.

  
  
  

  Learn binary math and how to use bitwise operators in javascript as they provide significant performance benefits when working with integers. Note that Javascript integers are signed 32 bit values.

  
  


• 
  

  Warning about destructuring

  
  
  

  Though you have not used destructuring, it is nowadays common to perform a swap using destructing. eg [queue[a], queue[b]] = [queue[b], queue[a]] and as a syntax it is very nice, but it is also currently extremely slow (About 10 times slower). You can get the same performance doing {const swap = [queue[b], queue[a]]; const swapped = [swap[1], swap[0]]; queue[a] = swapped[0]; queue[b] = swap[1]} to give a hint at how it's performed under the hood.

  
  
  

  I am sure this problem will be addressed soon and performance will follow standard styles, but for now be wary of destructuring in terms of performance.

  
  

Consistency

Try to be consistent with JavaScript. If you access an array item outside the range you get undefined. However in your code you return false It makes more sense to return undefined when the queue is empty.

The rewrite

The rewrite addresses some more performance issues. The swim function can perform a lot of swaps, while in reality you are only looking for a place to put a new value. Rather than add the new value to the queue, locate the new position and use splice to insert it. This save a lot of data movements. Thus swim is passed the value to swim up and be inserted

sink can also be improved by starting at 0, same with the queue, there is no need to hold an unused item at the start.

Removing the first item from queue means testing if there are items becomes if(queue.length)

If the queue is empty then undefined is returned. This eliminates the need to add conditional code to test for empty.

As sink is only called to shift a value from the queue, it may as well shift that value as well simplifying the delMax function now called shift

The code is much safer this way as it can not be misused, and performs a lot faster. It also reduces the source code size by half thus making it much easier to understand.

function Heap() {

    const queue = ;

    function sinkAndShift() {

        var k = 0, k2 = 1;

        while (k2 < queue.length) {

            if (queue[k] < queue[k2]) { 

                const tmp = queue[k]; // don't use destructuring.

                queue[k] = queue[k2];

                queue[k2] = tmp;

            } else { break }

            k2 = (k = k2) * 2;

        }

        return queue.shift();

    }

    function swim(val) {

        var k = queue.length - 1; 

        while (k > 0 && val > queue[k]) { k >>= 1 }

        queue.splice(k, 0, val);

    }    

    return Object.freeze({

        set value(k) {

            if (isNaN(k)) { throw new RangeError("Must be a number '" + k + "'") }

            swim(Number(k));

        },         

        shift() { return sinkAndShift() },

        get max() { return queue[0] },    

        get length() { return queue.length  },

    });

}



// usage



const heap = new Heap();

// or 

//const heap = new Heap;

// or 

//const heap = Heap();





heap.value = 100; // same as insert

heap.value = 101; // adds second value

heap.value = 102; 

heap.value = 103; 



console.log(heap.length); // outputs 4;

console.log(heap.max); // outputs 103;

console.log(heap.shift()); // outputs 103;

console.log(heap.length); // outputs 3;

console.log(heap.shift()); // outputs 102;

console.log(heap.shift()); // outputs 101;

console.log(heap.shift()); // outputs 100;

console.log(heap.shift()); // outputs undefined;



heap.value = "Monkey bread"; // will throw a range error