Data structures are important in computer programming for organizing, managing, and storing data in a quick and efficient manner. Data structures are an absolutely essential skill for any developer to have in their toolkit.
Today we will be continuing with the Data Structures 101 series, focusing on Heaps, a special tree-based data structure that implements a complete binary tree.
Today, we will cover:
- What is a Heap?
- Essential Operations in Heaps
- How to build a Max Heap
- How to build a Min Heap
- Heaps challenge: hands-on practice
- What to learn next
What is a Heap?
A heap is an advanced tree-based data structure used primarily for sorting and implementing priority queues. They are complete binary trees that have the following features:
- Every level is filled except the leaf nodes (nodes without children are called leaves).
- Every node has a maximum of 2 children.
- All the nodes are as far left as possible. This means that every child is to the left of his parent.
Heaps use complete binary trees to avoid holes in the array. A complete binary tree is a tree where each node has at most two children, and the nodes at all levels are full, except for the leaf nodes, which can be empty. Heaps are built based on the heap property, which compares the parent node key with its child node keys.
It is important to note that heaps are not always sorted. The key condition that they follow is that the largest or smallest element is placed on the root node (top) depending on if it is a Max or Min Heap. The Heap data structure is not the same as heap memory.
Pros and cons of Heaps
Pros:
- Garbage collection runs on the heap memory to free the memory used by the object.
- Heaps are flexible as memory can be allocated or removed in any order.
- Variables can be accessed globally.
- It helps to find the minimum and greatest number.
Cons:
- Compared to stacks, heaps take more time to execute.
- Memory management is more complicated in heap memory, as it is used globally.
- Heaps generally take more time to compute.
Applications of Heap Data Structure
Heaps are efficient for finding the min or max element in an array and are useful in order statistics and selection algorithms. The time complexity of getting the minimum/maximum value from a heap is O(1), (constant time complexity).
Priority queues are designed based on heap structures. It takes O(log(n)) time to insert (insert()) and delete (delete()) each element in the priority queue efficiently.
Heap-implemented priority queues are used in popular algorithms like:
- Prim’s algorithm
- Dijkstra’s algorithm
- Heapsort algorithm
Essential Operations in Heaps
The following are the essential operations you might use when implementing a heap data structure:
-
heapify: rearranges the elements in the heap to maintain the heap property. -
insert: adds an item to a heap while maintaining its heap property. -
delete: removes an item in a heap. -
extract: returns the value of an item and then deletes it from the heap. -
isEmpty: boolean, returns true if boolean is empty and false if it has a node. -
size: returns the size of the heap. -
getMax(): returns the maximum value in a heap
How to build a max Heap
Elements in a max heap follow the max heap property. This means that the key at the parent node is always greater than the key at both child nodes. To build a max heap:
- Create a new node at the beginning (root) of the heap.
- Assign it a value.
- Compare the value of the child node with the parent node.
- Swap nodes if the value of the parent is less than that of either child (to the left or right).
- Repeat until the largest element is at the root parent nodes (then you can say that the heap property holds).
These steps can also be followed when inserting new elements into a heap. The key here is whatever operation is being carried out on a Max Heap, the heap property must be maintained.
To remove/delete a root node in a Max Heap:
- Delete the root node.
- Move the last child node of the last level to the root.
- Compare the parent node with its children.
- If the value of the parent is less than the child nodes, swap them, and repeat until the heap property is satisfied.
Let’s take a look at what this looks like in code. In the next section, we will implement a max heap using JavaScript.
Implementing Max Heap in JavaScript
Before we get into building a Max Heap, take a look at some of the methods we’ll implement and what they do:
-
_percolateUp(): restores the heap property from a child node to a root node. -
_maxHeapify(): restores the heap property from a specific node down to leaf nodes. -
insert(): appends a given value to the heap array and rearranges elements based on their heap property. On every new insert, the heap grows uniformly, and the size increases by one. -
getMax(): returns the maximum value in the heap (root node) without modifying the heap. Note that the time complexity here is constant time O(1) -
removeMax(): returns and removes the maximum value in the heap (think ofpop()). The time complexity of this function is in O(log(n)).
If the heap size is greater than one, it stores the maximum value to a variable, swaps that value with the last leaf, and deletes the maximum value from the heap.
If the heap has just one element, it deletes and returns the value of that element, the last condition is if the heap is empty, it returns null.
The __percolateUp() method is called recursively on each parent node until the root is reached. For every node to be positioned following the max-heap property, we call the __maxHeapify() method at every index of that array, starting from the bottom of the heap.
class maxHeap {
constructor() {
this.heap = [];
this.elements = 0;
};
insert(val) {
if (this.elements >= this.heap.length) {
this.elements = this.elements + 1;
this.heap.push(val);
this.__percolateUp(this.heap.length - 1);
}
else {
this.heap[this.elements] = val;
this.elements = this.elements + 1;
this.__percolateUp(this.elements - 1);
}
};
getMax() {
if (this.elements !== 0)
return this.heap[0];
return null;
};
removeMax() {
let max = this.heap[0];
if (this.elements > 1) {
this.heap[0] = this.heap[this.elements - 1];
this.elements = this.elements - 1;
this.__maxHeapify(0);
return max
} else if (this.elements === 1) {
this.elements = this.elements - 1;
return max;
} else {
return null;
}
};
__percolateUp(index) {
const parent = Math.floor((index - 1) / 2);
if (index <= 0)
return
else if (this.heap[parent] < this.heap[index]) {
let tmp = this.heap[parent];
this.heap[parent] = this.heap[index];
this.heap[index] = tmp;
this.__percolateUp(parent);
}
};
__maxHeapify(index) {
let left = (index * 2) + 1;
let right = (index * 2) + 2;
let largest = index;
if ((this.elements > left) && (this.heap[largest] < this.heap[left])) {
largest = left
}
else if ((this.elements > right) && (this.heap[largest] < this.heap[right]))
largest = right
else if (largest !== index) {
const tmp = this.heap[largest];
this.heap[largest] = this.heap[index];
this.heap[index] = tmp;
this.__maxHeapify(largest);
}
};
buildHeap(arr) {
this.heap = arr;
this.elements = this.heap.length;
for (let i = this.heap.length - 1; i >= 0; i--) {
this.__maxHeapify(i);
}
};
};
let heap = new maxHeap();
How to build a min Heap
Intuitively, we can say that elements in a min heap follow the min heap property, as this is opposite to max heaps. The key at the parent node is always less than the key at both child nodes. To build a min heap:
- Create a new child node at the end of the heap (last level).
- Add the new key to that node (append it to the array).
- Move the child up until you reach the root node and the heap property is satisfied.
To remove/delete a root node in a min heap:
- Delete the root node.
- Move the key of the last child to the root.
- Compare the parent node with its children.
- If the value of the parent is greater than the child nodes, swap them, and repeat until the heap property is satisfied.
Implementing Min Heap in JavaScript
Before we get into building a min heap, note that its implementation is similar to that of Max Heap. minHeapify() restores the heap property. getMin() returns the minimum value in the heap (root node) without modifying the heap. And removeMin() deletes the minimum value and returns it.
class minHeap {
constructor() {
this.heap = []
this.elements = 0;
};
insert(val) {
if (this.elements >== this.heap.length) {
this.elements = this.elements + 1
this.heap.push(val);
this.__percolateUp(this.heap.length - 1);
}
else {
this.heap[this.elements] = val;
this.elements = this.elements + 1;
this.__percolateUp(this.elements - 1);
}
};
getMin() {
if (this.heap.length !== 0)
return this.heap[0];
return null;
}
removeMin() {
const min = this.heap[0];
if (this.elements > 1) {
this.heap[0] = this.heap[this.elements - 1];
this.elements = this.elements - 1;
this.__minHeapify(0);
return min;
} else if (this.elements == 1) {
this.elements = this.elements - 1;
return min;
} else {
return null;
}
};
__percolateUp(index) {
let parent = Math.floor((index - 1) / 2);
if (index <= 0)
return
else if (this.heap[parent] > this.heap[index]) {
let tmp = this.heap[parent];
this.heap[parent] = this.heap[index];
this.heap[index] = tmp;
this.__percolateUp(parent);
}
};
__minHeapify(index) {
let left = (index * 2) + 1;
let right = (index * 2) + 2;
let smallest = index;
if ((this.elements > left) && (this.heap[smallest] > this.heap[left])) {
smallest = left;
}
if ((this.elements > right) && (this.heap[smallest] > this.heap[right]))
smallest = right;
if (smallest !== index) {
let tmp = this.heap[smallest];
this.heap[smallest] = this.heap[index];
this.heap[index] = tmp;
this.__minHeapify(smallest);
}
}
buildHeap(arr) {
this.heap = arr;
this.elements = this.heap.length;
for (let i = this.heap.length - 1; i >= 0; i--) {
this.__minHeapify(i)
}
}
};
let heap = new minHeap();
heap.insert(12);
heap.insert(10);
heap.insert(-10);
heap.insert(100);
console.log(heap.getMin()); //you should get -10
let newheap = new minHeap();
let arr = [12, 6, 8, 3, 16, 4, 27];
newheap.buildHeap(arr) //builds this new heap with elements from the array
console.log(newheap.getMin()) //this logs 3
newheap.removeMin();
console.log(newheap.getMin())
Heaps Challenge: Convert Max Heap to Min Heap
Let's take our learning one step further with a hands-on challenge. Our goal here is to convert a max heap to a min heap. Follow along with our code solution to see how it's done.
Problem Statement: Implement a function convertMax(maxHeap) which will convert a binary max heap into a binary min heap where maxHeap is an array in the maxHeap format (i.e. the parent is greater than its children). Your output should be a converted array.
Sample Input:
maxHeap = [9,4,7,1,-2,6,5]
Sample Output:
result = [-2,1,5,9,4,6,7]
Problem:
function convertMax(maxHeap) {
return maxHeap
}
Solution:
function minHeapify(heap, index) {
var left = index * 2;
var right = (index * 2) + 1;
var smallest = index;
if ((heap.length > left) && (heap[smallest] > heap[left])) {
smallest = left
}
if ((heap.length > right) && (heap[smallest] > heap[right]))
smallest = right
if (smallest != index) {
var tmp = heap[smallest]
heap[smallest] = heap[index]
heap[index] = tmp
minHeapify(heap, smallest)
}
return heap;
}
function convertMax(maxHeap) {
for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--)
maxHeap = minHeapify(maxHeap, i)
return maxHeap
}
The code solution above can be run. We can consider the given maxHeap to be a regular array of elements and reorder it so that it represents a min heap accurately. The convertMax() function restores the heap property on all the nodes from the lowest parent node by calling the minHeapify() function on each.
The time complexity of building a heap is O(n). That is true for this problem as well.
function minHeapify(heap, index) {
var left = index * 2;
var right = (index * 2) + 1;
var smallest = index;
if ((heap.length > left) && (heap[smallest] > heap[left])) {
smallest = left
}
if ((heap.length > right) && (heap[smallest] > heap[right]))
smallest = right
if (smallest != index) {
var tmp = heap[smallest]
heap[smallest] = heap[index]
heap[index] = tmp
minHeapify(heap, smallest)
}
return heap;
}
function convertMax(maxHeap) {
for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--)
maxHeap = minHeapify(maxHeap, i)
return maxHeap
}
var maxHeap = [9,4,7,1,-2,6,5]
console.log(convertMax(maxHeap))
-->
[ -2, 1, 4, 5, 7, 6, 9 ]
What to learn next
Congratulations on making it to the end of this article. I hope you now have a good knowledge of how heaps work and can confidently build a heap with JavaScript.
Here are some common challenges that would help test your knowledge of heap data structure. You can expect to see these questions in a coding interview:
- Convert Max Heap to Min Heap
- Find k smallest element in an array
- Find k largest element in an array
- Check if a given array represents min heap or not
- Merge M-sorted lists of variable length
- Find the smallest range with at least one element from each of the given lists
To find answers to these questions and continue your learning, check out Educative’s course Data Structures for Coding Interviews in JavaScript. It will give you a detailed explanation of all common JavaScript data structures with solutions to real-world data structure problems. You'll become well equipped with all the different data structures they you leverage to write better code.
Happy learning!
Continue reading about JavaScript and data structures on Educative
- Top Data Structures and Algorithms every developer must know
- JavaScript Snake Game Tutorial: build a simple, interactive game
- Big-O Notation Cheat Sheet: quick answers to Big-O questions
Start a discussion
What is your favorite JavaScript data structure to work with? Was this article helpful? Let us know in the comments below!
Top comments (0)