Min Binary Heap in JavaScript

Concise Explanation!

Photo by Markus Spiske on Unsplash

Min Binary Heap:

1. A complete binary tree where parent nodes are always smaller than the child nodes.
2. Each Parent has at most two child nodes.
3. Parent is always smaller 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

Min Binary Heap Class:

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

class Name:
    MinBinaryHeap
properties:
    values = []

Insert in a Min 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 greater 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 min)

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 smaller than the element then swap. If both left and right children are smaller, swap with the smallest child.
• The child index you swapped to now becomes the new parent index.
• Keep looping and swapping until neither child is smaller 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 about Max Binary Heaps in JavaScript

Max Binary Heap in JavaScript

Binary Search Tree in JavaScript (Data Structures)

BFS in JavaScript (Data Structures)