Max Binary Heap in JavaScript

Max Binary Heap:

1. A complete binary tree where parent nodes are always larger than the child nodes.

2. Each Parent has at most two child nodes.

3. Parent is always greater than its children, but there are no guarantees between sibling nodes.

4. Since its a complete binary tree, so it is as compact as possible. All the children of each node are as full as they can be and left children are filled out first.

Relationship b/w Parent and Child nodes:

1. If a node is at an index - i

2. It’s left child is at - 2\i + 1*

3. It’s right child is at - 2\i + 2*

4. For any child at index ‘i’ it’s parent is at - floor((i-1) / 2)

Note: in this case we are assuming that starting index is 0

Max Binary Heap Class:

• We define our class MaxBinaryHeap

• The only property it requires in the constructor is a values property, which can be an empty list/array.

class Name:
    MaxBinaryHeap
properties:
    values = []

class MaxBinaryHeap {
    constructor() {
        this.values = [];
    }
}

---

Insert in a Max Binary Heap

TL;DR - Add to the end and bubble up.

Pseudocode:

1. Push the value on the values property on the heap.

2. Bubble the value upto it’s correct spot.

3. Bubble Up:

• Create a new variable called index which will store the index of the last element of the values array. (values.length-1).

• Create a variable parentIndex to store the index of current variable’s parent.

• Keep looping as long as the value of the element at the parentIndex is less than the value of the element at the child index.

• Swap the values of the elements at parentIndex and child’s index.

• Set the index to be the parentIndex and start over.

    insert(val) {
            this.values.push(val);
            this.bubbleUp();
        }
  
        bubbleUp() {
            let idx = this.values.length - 1;
            const element = this.values[idx];
            while(idx > 0) {
                let parentIdx = Math.floor((idx-1)/2);
                let parent = this.values[parentIdx];
                if(element <= parent) break;
                // swap the parent and the child
                this.values[parentIdx] = element;
                this.values[idx] = parent;
                // change idx to parentIdx
                idx = parentIdx;
            }
        }
  

---

Removing from a heap (extract max)

TL;DR:

• Remove the root.

• Replace with the most recently added node.

• Adjust the root. (sink down)

Pseudocode:

1. Swap the first value in the values property with the last one.

2. Pop from the values property, so you can return the value at the end.

3. Have the new root sink down to the correct spot:

• Parent index starts at 0 (the root)

• Find the index of the left child: 2*index + 1

• Find the index of the right child: 2*index + 2

• If the left or right child is greater than the element then swap. If both left and right children are larger, swap with the largest child.

• The child index you swapped to now becomes the new parent index.

• Keep looping and swapping until neither child is larger than the element.

• Return the old root.

    extractMax() {
            const max = this.values[0];
            const end = this.values.pop();
            if(this.values.length > 0) {
                this.values[0] = end;
                this.sinkDown();
            }
            return max;
        }
  
      sinkDown() {
          let idx = 0;
          const length = this.values.length;
          const element = this.values[0];
          while(true){
              let leftChildIdx = 2*idx + 1;
              let rightChildIdx = 2*idx + 2;
              let leftChild, rightChild;
              let swap = null;
              if(leftChildIdx < length) {
                  leftChild = this.values[leftChildIdx];
                  if(leftChild > element) {
                      swap = leftChildIdx;
                  }
              }
  
              if(rightChildIdx < length) {
                  rightChild = this.values[rightChildIdx];
                  if((swap === null && rightChild > element) || (swap !== null && rightChild > leftChild)) {
                      swap = rightChildIdx;
                  }
              }
  
              if(swap === null) break;
              this.values[idx] = this.values[swap];
              this.values[swap] = element;
              idx = swap;
          }
      }
  

---

Time Complexity:

• Insertion: O(log(n))

• Deletion: O(log(n))

• Building a heap: O(n)

Full code

// main class
class MaxBinaryHeap {
    constructor() {
        this.values = [];
    }

    // insert
    insert(val) {
        this.values.push(val);
        this.bubbleUp();
    }

    bubbleUp() {
        let idx = this.values.length - 1;
        const element = this.values[idx];
        while(idx > 0) {
            let parentIdx = Math.floor((idx-1)/2);
            let parent = this.values[parentIdx];
            if(element <= parent) break;
            // swap the parent and the child
            this.values[parentIdx] = element;
            this.values[idx] = parent;
            // change idx to parentIdx
            idx = parentIdx;
        }
    }

    // extract 
    extractMax() {
        const max = this.values[0];
        const end = this.values.pop();
        if(this.values.length > 0) {
            this.values[0] = end;
            this.sinkDown();
        }
        return max;
    }

    sinkDown() {
        let idx = 0;
        const length = this.values.length;
        const element = this.values[0];
        while(true){
            let leftChildIdx = 2*idx + 1;
            let rightChildIdx = 2*idx + 2;
            let leftChild, rightChild;
            let swap = null;
            if(leftChildIdx < length) {
                leftChild = this.values[leftChildIdx];
                if(leftChild > element) {
                    swap = leftChildIdx;
                }
            }

            if(rightChildIdx < length) {
                rightChild = this.values[rightChildIdx];
                if((swap === null && rightChild > element) || (swap !== null && rightChild > leftChild)) {
                    swap = rightChildIdx;
                }
            }

            if(swap === null) break;
            this.values[idx] = this.values[swap];
            this.values[swap] = element;
            idx = swap;
        }
    }
}