This JavaScript heap is implemented as a binary tree backed by an array. The expectation for readers of this blog post is experience creating an array backed binary tree. However, the purpose of this post is to create the easiest to comprehend heap implementation in JavaScript I could based solely on the definition found on Wikipedia. It may not follow some best practices but that is not the goal.

A binary tree is considered a heap when it satisfies two conditions:

• Shape property (completeness): The tree must be a complete binary tree. Every level, except possibly the last, is completely filled, and all nodes on the last level are as far left as possible.
• Heap property (ordering): Each node's value must be greater than or equal to its children's values in a max heap, or less than or equal to its children's values in a min heap.

A binary heap does not impose an ordering requirement between its left and right children. You might expect the smaller child to always appear on one side and the larger child on the other, but that is not required. The shape property must still be preserved, but the only ordering constraint is between each parent and its children.

The starting point for the constructor's loop was confusing to me at first. Why begin just before the middle of the array and call siftDown while moving back toward the root?

For a zero-based array of length n, every node from index Math.floor(n / 2) through n - 1 is a leaf. Each leaf is already a valid one-node heap, so the last internal node—and therefore the last possible starting point for siftDown—is at index Math.floor(n / 2) - 1.

Starting with the last parent, siftDown compares the node with its children. For a max heap, it swaps with the larger child when that child is larger than the node. For a min heap, it swaps with the smaller child when that child is smaller than the node. The process continues down the tree until the heap property is restored.

Working backward from the last parent to the root turns every subtree into a heap. The same siftDown operation is useful after pop moves the final array element to the root.

To insert a value, start by appending it to the array. Completeness is preserved because the new value becomes the next available leaf.

Then call siftUp from the new final index. Compare the leaf with its parent and swap when the heap property is violated. Continue one ancestor at a time until the value reaches its correct place or becomes the root.

In this example, 85 is appended at index 7. Since 85 > 40, it first swaps with the value at index 3, then continues comparing itself with the ancestors at indexes 1 and 0 until the max-heap property is restored.

Now here is some code. Starting with a max heap in ~60 lines:

function siftDown(a, startIndex) {
    let curIndex = startIndex;
    while(true) {
        const leftIndex = 2 * curIndex + 1;
        const rightIndex = 2 * curIndex + 2;

        let largestIndex = curIndex;

        if (leftIndex < a.length && a[leftIndex] > a[largestIndex]) largestIndex = leftIndex;
        if (rightIndex < a.length && a[rightIndex] > a[largestIndex]) largestIndex = rightIndex;
        if (largestIndex === curIndex) break;

        const tmp = a[largestIndex];
        a[largestIndex] = a[curIndex];
        a[curIndex] = tmp;

        curIndex = largestIndex; 
    }
}

function siftUp(a, startIndex) {
    let curIndex = startIndex;
    const moveUpTree = (i) => Math.floor((i - 1) / 2);
    while(curIndex > 0) {
        const ancestorIndex = moveUpTree(curIndex);
        if (a[curIndex] <= a[ancestorIndex]) {
            break;
        }

        const tmp = a[ancestorIndex];
        a[ancestorIndex] = a[curIndex];
        a[curIndex] = tmp;
        
        curIndex = ancestorIndex;
    }
}

// TODO: Make generic and add comparator
class MaxHeap {
    constructor(arr=[]) {
        this._a = [...arr];

        const beforeLeaves = Math.floor(this._a.length / 2) - 1;
        for (let i=beforeLeaves; i>=0; i--) siftDown(this._a, i);
    }

    pop() {
        if (this._a.length === 0) return undefined;
        if (this._a.length === 1) return this._a.pop();
        const ret = this._a[0];

        this._a[0] = this._a.pop();
        siftDown(this._a, 0);

        return ret;
    }

    insert(val) {
        this._a.push(val);
        siftUp(this._a, this._a.length-1);
    }

    showArr() {
        console.log(this._a);
    }
}

const mh = new MaxHeap([5,2,7,3,1,0,9]);
mh.showArr();
console.log(mh.pop());
console.log(mh.pop());
console.log(mh.pop());
mh.insert(11);
mh.insert(10);
console.log(mh.pop());
mh.showArr();
const mhEmpty = new MaxHeap([]);
console.log(mhEmpty.pop());
mhEmpty.insert(1);
mhEmpty.insert(10);
mhEmpty.insert(3);
mhEmpty.insert(6);
mhEmpty.insert(2);
console.log(mhEmpty.pop());

Some TDD would be perfect for a longer blog post. Leaving the abstraction of this so all that is needed is a comparator to change this from a MaxHeap class to a generic Heap class. Also, this implementation expects Number types. NaN, undefined, and mixed types are not rejected and can produce unexpected results.