Max Binary Heap in JavaScript

Concise explanation!

Photo by Alvan Nee on Unsplash

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 = []

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.

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.

Time Complexity:

• Insertion: O(log(n))
• Deletion: O(log(n))
• Building a heap: O(n)

Full code

Also, read

Binary Search Tree in JavaScript (Data Structures)

Queues in JavaScript (Data Structures)

Reduce Method in JavaScript

Filter method in JavaScript