Heap Sort Using Javascript
Heap is a complete binary tree(each root has max available values). A complete binary tree is a binary tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left. A binary tree has 2**(h+1) -1 nodes(h is the height of the binary tree).
There are two types of heap:
- Max heap
- Min Heap
Max Heap: Max heap is a complete binary tree in which each node(element) have value greater than or equals to its child nodes(descendants).
Min heap: Min heap is a complete binary tree in which each node(element) have value less than or equals to its child nodes(descendants).
Array representation of min heap : [1,3,2,4,6,5] and of max heap: [6,5,3,4,2,1]
For the explanation, let’s use Max heap, and array [6,5,3,4,2,1].
There are few things we need to understand before we jump into coding.
- How to find the parent of an element?
- How to find the left child of an element?
- How to find the right child of an element?
- Is the current node a leaf node(leaf node is a node that has no child)?
Parent of an element: To find parent of an element, the formula is. Math.floor((index-1)/2). let’s suppose we need to find the parent of element 4 that is currently at index 4.
const parent = Math.floor((index-1)/2);// that is Math.floor(4-1)/2 = 1(index of parent),
// which is 5. so 5 is the parent of 4.Left child of an element: To find left child of an element, the formula is (2*index)+1. Let’s suppose we need to find the left child of 5 which is at index 1.
const leftChild = (2*index)+1; // that is (2*1)+1 = 3(index of left child)
// according to this 4 which is at index 3 is the left child of 5.Right child of an element: To find right child of an element, the formula is (2*index)+2. Let’s suppose we need to find the right child of 5 which is at index 1.
const rightChild = (2*index)+2; // that is (2*1)+2 = 4(index of right child)
// according to this 2 which is at index 4 is the right child of 3.Checking if current node is a leaf node : In order to check if the current index is leaf we need to check if current index is more than the half of length of array and less than length of array. This means there are no child nodes.
//so we can check through
const leftChild = index >= Math.floor(this.value.length / 2) &&
index <= this.value.length - 1“In this blog, we’ll also go through few concepts”
- Insertion
- Deletion
- Heapify
- And finally the working on Heap sort
Insertion
Let’s suppose we have an array representation of max heap that is [6,5,3,4,2,1] and we want to insert a new element in the heap, then we need to push the element into the array and check with its parent if the condition satisfies for the max heap or not(basically if parent is greater than or equal to child or not.). if the current node doesn't satisfy the condition than we need to swap them and check for the new node.
Insertion follow the approach of heapify up, as we are checking from leaf toward root.
Time complexity of Insertion: The number of swap happens at the time of insertion can be maximum to the height of the tree i.e- (log n), so the worst case time complexity of insertion is O(log n).
Deletion
In our array [6,5,3,4,2,1], if you want to remove an element, it should be the root element, so in our case the root is 6. Once we remove 6, then the last element in the array (i.e - 1) will take the place of root element. Once that is done, then we need adjust the tree and compare with the left and child node with the new root element, if the current heap satisfies the properties of a max heap or not. if not then we need to swap them.
Deletion follow the approach of heapify Down, as we are comparing from root toward leaf.
Time complexity of Deletion: The number of swap happens at the time of deletion can be maximum to the height of the tree i.e- (log n), so the worst case time complexity of insertion is O(log n).
Heapify
Heapify is a process of creating a heap data structure from a binary tree represented using array. Once we remove or add an element to the heap, we need to do heapifyUp(after adding) and heapifyDown(after deleting).
HeapifyUp means processing the elements in an heap from leaf to root and processing if the elements are in order and satisfy max heap or not, if not we need to swap them.
HeapifyDown means processing the elements in an heap from root to leaf and processing if the elements are in order and satisfy max heap or not, if not we need to swap them.
Heapify has a time complexity of O(n).
Heap sort
Heap sort basically is a concept of first creating a heap and then deleting the heap and build a sorted array. As we delete, we get the maximum element from the available array. So we’ll go through the working of both of these processes.
- Build a heap.
- Delete element from heap.
Let’s suppose we have a initial array [10,20,15,30,40]
Let’s cover up few of the important functions that we are going to use for our heap sort.
- To find the parent of an element at index
// to fetch parent of the node
// the formulae is (index - 1 /2)
parent(index) {
return Math.floor((index - 1) / 2);
}- To find left node index
// fetch index of left node from index of parent node
leftNode(index) {
return 2 * index + 1;
}- To find index of right node
// fetch index of right node from index of parent node
rightNode(index) {
return 2 * index + 2;
}- To find is current node is leaf node or not
//if the index is more than the half of length of array and index is less than length of array, means,
//there is no child node
isLeaf(index) {
return (
index >= Math.floor(this.value.length / 2) &&
index <= this.value.length - 1
);
}- swap two values
// swap functionality
swap(index, target) {
[this.value[index], this.value[target]] = [
this.value[target],
this.value[index],
];
}- To perform heapifyUp
// this will check each node and compare if the current node is at right path or not while comparing it with its parent
// this is a leaf to root approach
heapifyUp(index) {
let currentNodeIndex = index;
let parentNodeIndex = this.parent(currentNodeIndex);
// we need to perform while loop until we reach the top node and value of child is more than parent node
while (
parentNodeIndex >= 0 &&
currentNodeIndex > 0 &&
this.value[currentNodeIndex] > this.value[parentNodeIndex]
) {
// current child is greater than parent so we need to swap them
this.swap(currentNodeIndex, parentNodeIndex);
// now we need to set the current parent as child and find the new parent for the child node
currentNodeIndex = parentNodeIndex;
parentNodeIndex = this.parent(parentNodeIndex);
}
}- To perform HeapifyDown
// if we remove an element from the heap , we need to perform heapifyDown
// so that we compare if the nodes are at right position
// this is root to leaf approach, there we compare the childrens with the current node
heapifyDown(index) {
// we need to check if current node is not a leaf
if (!this.isLeaf(0)) {
// fetch left node
let leftNode = this.leftNode(index);
// fetch right node
let rightNode = this.rightNode(index);
let biggerNode = index;
// we need to compare if the left and right node are bigger or not
if (this.value[biggerNode] < this.value[leftNode]) {
biggerNode = leftNode;
}
if (this.value[biggerNode] < this.value[rightNode]) {
biggerNode = rightNode;
}
// checking if we have any mismatch, if yes swap
if (biggerNode != index) {
this.swap(index, biggerNode);
this.heapifyDown(biggerNode);
}
}
}- To extract maximum element from the heap
// method to fetch the top element from the heap
extractMax() {
if (!this.value.length) return;
// fetch the largest value
const largestValue = this.value[0];
// replace with last node
this.value[0] = this.value.pop();
// once we remove the top element, we need to perform heapifyDown to take the elements to its right place in heap
this.heapifyDown(0);
return largestValue;
}- Build a heap from provided array
// build an heap from the array
buildHeap(heapNodes) {
this.value = heapNodes;
for (let i = Math.floor(this.value.length / 2); i >= 0; i--) {
// we need to perform heapifyDown to put elements to its right place
this.heapifyDown(i);
}
}Let’s jump into the working of heap sort by combining all the available functions.
we’ll make use of javascript classes to build this algorithm.Below is the heap sort in code.
class HeapSort {
constructor() {
this.value = []; // store the nodes
}
// to fetch parent of the node
// the formulae is (index -1 /2)
parent(index) {
return Math.floor((index - 1) / 2);
}
// fetch index of left node from index of parent node
leftNode(index) {
return 2 * index + 1;
}
// fetch index of right node from index of parent node
rightNode(index) {
return 2 * index + 2;
}
//if the index is more than the half of length of array and index is less than length of array, means,
//there is no child node
isLeaf(index) {
return (
index >= Math.floor(this.value.length / 2) &&
index <= this.value.length - 1
);
}
// swap functionality to swap nodes if conditions not meet
swap(index, target) {
[this.value[index], this.value[target]] = [
this.value[target],
this.value[index],
];
}
//Adding a node to the last of the array and then perform heapifyUp to put node at its right position
addNode(node) {
this.value.push(node);
//heapify up to put the node at right point
this.heapifyUp(this.value.length - 1);
}
// this will check each node and compare if the current node is at right path or not while comparing it with its parent
// this is a leaf to root approach
heapifyUp(index) {
let currentNodeIndex = index;
let parentNodeIndex = this.parent(currentNodeIndex);
// we need to perform while loop until we reach the top node and value of child is more than parent node
while (
parentNodeIndex >= 0 &&
currentNodeIndex > 0 &&
this.value[currentNodeIndex] > this.value[parentNodeIndex]
) {
// current child is greater than parent so we need to swap them
this.swap(currentNodeIndex, parentNodeIndex);
// now we need to set the current parent as child and find the new parent for the child node
currentNodeIndex = parentNodeIndex;
parentNodeIndex = this.parent(parentNodeIndex);
}
}
// if we remove an element from the heap , we need to perform heapifyDown
// so that we compare if the nodes are at right position
// this is root to leaf approach, there we compare the childrens with the current node
heapifyDown(index) {
// we need to check if current node is not a leaf
if (!this.isLeaf(0)) {
// fetch left node
let leftNode = this.leftNode(index);
// fetch right node
let rightNode = this.rightNode(index);
let biggerNode = index;
// we need to compare if the left and right node are bigger or not
if (this.value[biggerNode] < this.value[leftNode]) {
biggerNode = leftNode;
}
if (this.value[biggerNode] < this.value[rightNode]) {
biggerNode = rightNode;
}
// checking if we have any mismatch, if yes swap
if (biggerNode != index) {
this.swap(index, biggerNode);
this.heapifyDown(biggerNode);
}
}
}
// method to fetch the top element from the heap
extractMax() {
if (!this.value.length) return;
// fetch the largest value
const largestValue = this.value[0];
// replace with last node
this.value[0] = this.value.pop();
// once we remove the top element, we need to perform heapifyDown to take the elements to its right place in heap
this.heapifyDown(0);
return largestValue;
}
// build an heap from the array
buildHeap(heapNodes) {
this.value = heapNodes;
for (let i = Math.floor(this.value.length / 2); i >= 0; i--) {
// we need to perform heapifyDown to put elements to its right place
this.heapifyDown(i);
}
}
}You can test the working through supplying an array through buildHeap functionality.
const heap = new HeapSort();
heap.buildHeap([10,20,15,30,40]);
console.log(heap.extractMax());
console.log(heap.extractMax());
console.log(heap.extractMax());
console.log(heap.extractMax());
console.log(heap.extractMax());Response:
You can test through adding nodes:
const heap = new HeapSort();
heap.addNode(10);
heap.addNode(20);
heap.addNode(15);
heap.addNode(30);
heap.addNode(40);
console.log(heap.extractMax());
console.log(heap.extractMax());
console.log(heap.extractMax());
console.log(heap.extractMax());
console.log(heap.extractMax());The response is same as above.
I have tried to comment every functional part of the algorithm in the code. if you still have any issues understanding it, leave a comment and i’ll try to answer your queries.
Stay tuned for more to come, If you are new here, do checkout our Algorithms using Javascript blog, we are covering few of the most commonly used algorithms using javascript.
In the next blog, we’ll go through Breadth first search
