The heap property
This property can be considered a constraint for defining a tree, a certain structure that must be followed while constructing a tree. Heap defines a relationship between the parent nodes and its child nodes, there are two types of heaps and therefore there are two types of relationship that can exist between the parent node and the child node:
- Max-Heap: The value of the parent nodes must always be greater or equal to the child nodes
- Min-heap: The value of the parent nodes must always be smaller or equal to the child nodes
A representation of the Min-heap is:
(Image by Wikipedia)
As you can see, in the tree that the parent nodes have lower values than their child nodes
Ar representation of the Max-heap is:
(Image by Wikipedia)
You can see that the parent nodes have values greater than their child nodes.
Array Representation
Heaps in a programming language are represented in the form of an array, an example of the heap array constructed from the max-heap tree above is:
When representing a binary heap in the form of an array, you use the following expression to deduce the following:
- Left child = i * 2
- Right child = i * 2 + 1
- Parent = i / 2
Where “i” stands for the index of the array. Talking about indexes, when we implement heap structures using an array, we put a “null” in the first index which is the index 0.
Visual Representation of working of a heap
For a virtual representation of the working of a min-heap and how are the values inserted into the heap, we can head over to the heap visualizer by the University of San Francisco by clicking here
Insert values into the heap, and you’ll notice how a new element is inserted into the heap due to the animation:
Working of Heap
A Binary Heap has two main functions:
- First is to add the new element at its appropriate position
- The second function is to remove the root value
Adding a new element in the heap
A new element is always added at the end of the array, and then it is checked against its parent and if it goes against the heap property then it is exchanged with its parent. The element is checked until it has been compared with the root node of the heap (root node is the first node of the heap).
Removing an element from the heap
Whenever you want to remove or fetch a value from the heap, you always fetch the root node’s value. That is why this value is the smallest value if it is a min-heap and the largest value if it is a max-heap. When the root node is removed from the heap, the last node of the array takes its place, then it is compared with its child nodes to match the condition of the heap. If it doesn’t match the condition, it is replaced with its child node and then checked with further child nodes. A much better way to explain this is by using the live heap viewer as shown below:
You can observe the removal process by observing the gif above.
Implementing the binary heap in JavaScript
We are going to be implementing the min-heap step by step, we start of the process by creating a new function with the following lines of code:
// Rest of the min-heap code will be present inhere
}
The first step is to create an array and set the value at index 0 as null:
Then we are going to create the insert function using the following lines of code:
heap.push(num);
if (heap.length>2) {
letidx = heap.length - 1;
while (heap[idx] = 1) {
[heap[Math.floor(idx / 2)], heap[idx]] = [
heap[idx],
heap[Math.floor(idx / 2)],
];
if (Math.floor(idx / 2) >1) {
idx = Math.floor(idx / 2);
} else {
break;
}
}
}
}
};
The following things are happening in this code snippet:
- A new element num is added at the last index of the array
- If the array length is bigger than 2 elements then we check the new element with its parent node
- If the element is smaller than its parent node, then it is replaced with its parent node, otherwise we deduce that the heap in in correct order
- If the element is replaced with its parent node in the previous step, then we again compare it with its new parent until we deduce that heap is in correct order or the element becomes the root node
The next step is to implement the remove function with the following lines of code:
let smallest = heap[1];
if (heap.length>2) {
heap[1] = heap[heap.length - 1];
heap.splice(heap.length - 1);
if (heap.length == 3) {
if (heap[1] > heap[2]) {
[heap[1], heap[2]] = [heap[2], heap[1]];
}
return smallest;
}
leti = 1;
letleft = 2 * i;
letright = 2 * i + 1;
while (heap[i] >= heap[left] || heap[i] >= heap[right]) {
if (heap[left] < heap[right]) {
[heap[i], heap[left]] = [heap[left], heap[i]];
i = 2 * i;
} else {
[heap[i], heap[right]] = [heap[right], heap[i]];
i = 2 * i + 1;
}
left = 2 * i;
right = 2 * i + 1;
if (heap[left] == undefined || heap[right] == undefined) {
break;
}
}
} elseif (heap.length == 2) {
heap.splice(1, 1);
} else {
return null;
}
return smallest;
};
The following steps are happening in the above code snippet:
- We remove the root node as it is the smallest node of the heap
- If the heap only has two elements, then the 2nd element becomes the root node
- If the heap has 3 elements then the smallest out of the 2nd and 3rd element becomes the root node
- If the element has more than 3 elements, then the last element of the heap becomes the root node
- Then this new root node is compared with its child nodes and is replaced with the smaller node and is against compared with the new child nodes (for replacement we are using the object destructuring method)
- This process of comparing the element with the child nodes is repeated until it reaches a point where it is smaller than both of the child nodes or it becomes the last node in the array.
The next step is to create a function that will display us the heap array to the console, we do that by using the following lines of code:
console.log(heap);
};
The complete code snippet of implementing the min-heap data structure is:
let heap = [null];
this.insert = function (num) {
heap.push(num);
if (heap.length>2) {
letidx = heap.length - 1;
while (heap[idx] = 1) {
[heap[Math.floor(idx / 2)], heap[idx]] = [
heap[idx],
heap[Math.floor(idx / 2)],
];
if (Math.floor(idx / 2) >1) {
idx = Math.floor(idx / 2);
} else {
break;
}
}
}
}
};
this.remove = function () {
let smallest = heap[1];
if (heap.length>2) {
heap[1] = heap[heap.length - 1];
heap.splice(heap.length - 1);
if (heap.length == 3) {
if (heap[1] > heap[2]) {
[heap[1], heap[2]] = [heap[2], heap[1]];
}
return smallest;
}
leti = 1;
let left = 2 * i;
let right = 2 * i + 1;
while (heap[i] >= heap[left] || heap[i] >= heap[right]) {
if (heap[left] < heap[right]) {
[heap[i], heap[left]] = [heap[left], heap[i]];
i = 2 * i;
} else {
[heap[i], heap[right]] = [heap[right], heap[i]];
i = 2 * i + 1;
}
left = 2 * i;
right = 2 * i + 1;
if (heap[left] == undefined || heap[right] == undefined) {
break;
}
}
} elseif (heap.length == 2) {
heap.splice(1, 1);
} else {
returnnull;
}
return smallest;
};
this.show = function () {
console.log(heap);
};
};
What we need to do now is to create a new min-heap using the MinHeap function that we just created and then add elements to it using the insert and display the heap. To do this we make a new variable and map it on the MinHeap using the following lines of code:
Next, up let’s add values to the heap using the following lines of code:
newMinHeap.insert(61);
newMinHeap.insert(138);
newMinHeap.insert(82);
newMinHeap.insert(27);
newMinHeap.insert(35);
Now, we call the show function to display the heap array onto the console:
We get the following result on our console:
As you can see, the first element of the array is null. The rest of the nodes are not bigger than their child nodes. For example, if we take the node with the value 35. The left and the right child are as:
You can clearly see, the parent (35) is smaller than its left child (82) and its right child (61) as well. Similarly, every parent node is smaller then its child node, therefore we can deduce that our code is working perfectly
Similarly, by just changing the condition for comparing for being the parent node being smaller than the child to the parent node being bigger than the child node we can implement the Max-heap using the following lines of code:
let heap = [null];
this.insert = function (num) {
heap.push(num);
if (heap.length>2) {
letidx = heap.length - 1;
while (heap[idx] > heap[Math.floor(idx / 2)]) {
if (idx>= 1) {
[heap[Math.floor(idx / 2)], heap[idx]] = [
heap[idx],
heap[Math.floor(idx / 2)],
];
if (Math.floor(idx / 2) >1) {
idx = Math.floor(idx / 2);
} else {
break;
}
}
}
}
};
this.remove = function () {
let smallest = heap[1];
if (heap.length>2) {
heap[1] = heap[heap.length - 1];
heap.splice(heap.length - 1);
if (heap.length == 3) {
if (heap[1] < heap[2]) {
[heap[1], heap[2]] = [heap[2], heap[1]];
}
return smallest;
}
leti = 1;
let left = 2 * i;
let right = 2 * i + 1;
while (heap[i] <= heap[left] || heap[i] heap[right]) {
[heap[i], heap[left]] = [heap[left], heap[i]];
i = 2 * i;
} else {
[heap[i], heap[right]] = [heap[right], heap[i]];
i = 2 * i + 1;
}
left = 2 * i;
right = 2 * i + 1;
if (heap[left] == undefined || heap[right] == undefined) {
break;
}
}
} elseif (heap.length == 2) {
heap.splice(1, 1);
} else {
returnnull;
}
return smallest;
};
this.show = function () {
console.log(heap);
};
};
That is it, you have successfully implemented a Binary heaps in JavaScript
Conclusion
Binary heaps are the parietal implementation of a binary tree having the condition of having at-most two child nodes for each parent node, and the complete structure of the binary tree. Meaning that the levels of the tree will be filled from the left-side or left-child and then the right-child.
Binary heaps are part of advanced data structures, and there are two types of binary tree: one of them is called the min heap while the other one is called the max heap. In the min-heap, the parent nodes have smaller values than their child nodes and the values of the sibling nodes don’t matter.
Similarly, in max-heap, the values of the parent node is always greater than their child node and the values of the sibling nodes don’t matter. In this post, we learned about heaps and their implementation in vanilla javascript and at the end we tested out our implementation.
