Heap is a specialized tree-based data structure developed by J.W.J Williams in 1964 as data structure for heap sort.
In this tutorial, we will learn about the heap data structure and how to implement a binary heap in javascript.
What is heap data structure?.
Heap is one efficient implementation of an abstract data structure called a priority queue.
In a heap, the highest (or lowest) priority element is always stored at the root, thus priority queue is often referred to as heaps irrespective of their implementation.
Heap is the most useful data structure when it is necessary to repeatedly remove the object with the highest (or lowest) priority.
One of the most common implementations of the heap is the binary heap which is basically a binary tree.
A binary heap is basically a binary tree with two additional properties.
- Shape property: It must be a complete binary tree, which means all the levels of the tree, except the deepest (last) one are fully filled. In case the last level of the tree is not complete, the nodes of that level are filled from left to right.
- Heap property: All nodes are either greater than or equal to or less than or equal to each of its children. If the parent nodes are greater than their child nodes, the heap is called a Max-Heap, and if the parent nodes are smaller than their child nodes, the heap is called Min-Heap.
List of operations performed on binary heap.
- insert(num): Add a new key to the heap.
- delete(num): Removes a key from the heap.
- heapify: Create a (min or max) heap from the given array.
- findMax or (findMin): Return the max element from the heap or (min).
- extractMax or (extractMin): Remove and return the max element from the heap or (min).
- deleteMax or (deleteMin): Remove the max element from the heap or (min).
- size: Return the size of the heap.
- isEmpty: Is heap empty or not?.
- getList: Get the heap as an array.
Implementing binary heap data structure in Javascript.
Binary heaps can be represented using an array with certain mathematical calculations.
If the index of any element in the array is i, the element in the index 2i+1 will become the left child, and the element in the 2i+2 index will become the right child. Also, the parent of any element at index i is given by the lower bound of (i-1)/2.
Thus we can create the binary heap using an array rather than using a tree.
function BinaryHeap(){
let list = [];
//other operations will go here.
}
Heapify
The first operation which we will be adding is heapify, because either after inserting or deleting a new element in the heap we will have to heapify it to retain the form.
To build a max-heap from any tree, we can start heapifying each sub-tree from the bottom up and end up with a max-heap. Repeat this for all the elements including the root element.
In the case of a complete tree, the first index of a non-leaf node is given by n/2 - 1. All other nodes after that are leaf-nodes and thus don’t need to be heapified.
//Heapify
this.maxHeapify = (arr, n, i) => {
let largest = i;
let l = 2 * i + 1; //left child index
let r = 2 * i + 2; //right child index
//If left child is smaller than root
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
// If right child is smaller than smallest so far
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
// If smallest is not root
if (largest != i) {
let temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// Recursively heapify the affected sub-tree
this.maxHeapify(arr, n, largest);
}
}
Inserting a new element in the heap.
To add a new element, we first check if the list is empty or not. If it is empty then push the element directly, else we will have to heapify the list after addition.
//Insert Value
this.insert = (num) => {
const size = list.length;
if(size === 0){
list.push(num);
}else{
list.push(num);
for (let i = parseInt(list.length / 2 - 1); i >= 0; i--) {
this.maxHeapify(list, list.length, i);
}
}
}
Removing an element from the heap.
Removing a node is 4 step process.
- Find the element in the array.
- Swap the element with the last element.
- Remove the last element.
- Heapify the list.
//Remove value
this.delete = (num) => {
const size = list.length;
//Get the index of the number to be removed
let i;
for(i = 0; i < size; i++){
if(num === list[i]){
break;
}
}
//Swap the number with last element
[list[i], list[size - 1]] = [list[size - 1], list[i]];
//Remove the last element
list.splice(size - 1);
//Heapify the list again
for (let i = parseInt(list.length / 2 - 1); i >= 0; i--) {
this.maxHeapify(list, list.length, i);
}
}
Find max from the heap
As the list is already max heapified, we just need to return the root element because it is the max.
//Return max value this.findMax = () => list[0];
Delete max from the heap
Delete the root to remove the max. We can use the exisiting delete method for it.
//Remove max val
this.deleteMax = () => {
this.delete(list[0]);
}
Extract max from the heap
Store the max value in a variable and then delete it from the heap, after that return the value.
//Remove and return max value
this.extractMax = () => {
const max = list[0];
this.delete(max);
return max;
}
Size of the heap
//Size this.size = () => list.length;
IsEmpty check
//IsEmpty this.isEmpty = () => list.length === 0;
Get the heap
//Return head this.getList = () => list;
Complete code of binary heap data structure implemented in Javascript.
function BinaryHeap(){
let list = [];
//Heapify
this.maxHeapify = (arr, n, i) => {
let largest = i;
let l = 2 * i + 1; //left child index
let r = 2 * i + 2; //right child index
//If left child is smaller than root
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
// If right child is smaller than smallest so far
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
// If smallest is not root
if (largest != i) {
let temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// Recursively heapify the affected sub-tree
this.maxHeapify(arr, n, largest);
}
}
//Insert Value
this.insert = (num) => {
const size = list.length;
if(size === 0){
list.push(num);
}else{
list.push(num);
//Heapify
for (let i = parseInt(list.length / 2 - 1); i >= 0; i--) {
this.maxHeapify(list, list.length, i);
}
}
}
//Remove value
this.delete = (num) => {
const size = list.length;
//Get the index of the number to be removed
let i;
for(i = 0; i < size; i++){
if(list[i] === num){
break;
}
}
//Swap the number with last element
[list[i], list[size - 1]] = [list[size - 1], list[i]];
//Remove the last element
list.splice(size - 1);
//Heapify the list again
for (let i = parseInt(list.length / 2 - 1); i >= 0; i--) {
this.maxHeapify(list, list.length, i);
}
}
//Return max value
this.findMax = () => list[0];
//Remove max val
this.deleteMax = () => {
this.delete(list[0]);
}
//Remove and return max value
this.extractMax = () => {
const max = list[0];
this.delete(max);
return max;
}
//Size
this.size = () => list.length;
//IsEmpty
this.isEmpty = () => list.length === 0;
//Return head
this.getList = () => list;
}
Input: const heap = new BinaryHeap(); heap.insert(3); heap.insert(4); heap.insert(9); heap.insert(5); heap.insert(2); console.log(heap.getList()); heap.delete(9); console.log(heap.getList()); heap.insert(7); console.log(heap.getList()); Output: [9, 5, 4, 3, 2] [5, 3, 4, 2] [7, 5, 4, 2, 3]
Binary heap with Min-Heap
function BinaryHeap(){
let list = [];
//Heapify
this.minHeapify = (arr, n, i) => {
let smallest = i;
let l = 2 * i + 1; //left child index
let r = 2 * i + 2; //right child index
//If left child is smaller than root
if (l < n && arr[l] < arr[smallest]) {
smallest = l;
}
// If right child is smaller than smallest so far
if (r < n && arr[r] < arr[smallest]) {
smallest = r;
}
// If smallest is not root
if (smallest != i) {
let temp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = temp;
// Recursively heapify the affected sub-tree
this.minHeapify(arr, n, smallest);
}
}
//Insert Value
this.insert = (num) => {
const size = list.length;
if(size === 0){
list.push(num);
}else{
list.push(num);
//Heapify
for (let i = parseInt(list.length / 2 - 1); i >= 0; i--) {
this.minHeapify(list, list.length, i);
}
}
}
//Remove value
this.delete = (num) => {
const size = list.length;
//Get the index of the number to be removed
let i;
for(i = 0; i < size; i++){
if(list[i] === num){
break;
}
}
//Swap the number with last element
[list[i], list[size - 1]] = [list[size - 1], list[i]];
//Remove the last element
list.splice(size - 1);
//Heapify the list again
for (let i = parseInt(list.length / 2 - 1); i >= 0; i--) {
this.minHeapify(list, list.length, i);
}
}
//Return min value
this.findMin = () => list[0];
//Remove min val
this.deleteMin = () => {
this.delete(list[0]);
}
//Remove and return min value
this.extractMin = () => {
const min = list[0];
this.delete(min);
return min;
}
//Size
this.size = () => list.length;
//IsEmpty
this.isEmpty = () => list.length === 0;
//Return head
this.getList = () => list;
}
Input: const heap = new BinaryHeap(); heap.insert(3); heap.insert(4); heap.insert(9); heap.insert(5); heap.insert(2); console.log(heap.getList()); heap.delete(9); console.log(heap.getList()); heap.insert(7); console.log(heap.getList()); Output: [2, 3, 9, 5, 4] [2, 3, 4, 5] [2, 3, 4, 5, 7]
Class based implementation of binary heap in javascript.
class BinaryHeap{
constructor(){
this.list = [];
}
//Heapify
maxHeapify = (arr, n, i) => {
let largest = i;
let l = 2 * i + 1; //left child index
let r = 2 * i + 2; //right child index
//If left child is smaller than root
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
// If right child is smaller than smallest so far
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
// If smallest is not root
if (largest != i) {
let temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// Recursively heapify the affected sub-tree
this.maxHeapify(arr, n, largest);
}
}
//Insert Value
insert = (num) => {
const size = this.list.length;
if(size === 0){
this.list.push(num);
}else{
this.list.push(num);
//Heapify
for (let i = parseInt(this.list.length / 2 - 1); i >= 0; i--) {
this.maxHeapify(this.list, this.list.length, i);
}
}
}
//Remove value
delete = (num) => {
const size = this.list.length;
//Get the index of the number to be removed
let i;
for(i = 0; i < size; i++){
if(num === this.list[i]){
break;
}
}
//Swap the number with last element
[this.list[i], this.list[size - 1]] = [this.list[size - 1], this.list[i]];
//Remove the last element
this.list.splice(size - 1);
//Heapify the list again
for (let i = parseInt(this.list.length / 2 - 1); i >= 0; i--) {
this.maxHeapify(this.list, this.list.length, i);
}
}
//Return max value
findMax = () => this.list[0];
//Remove max val
deleteMax = () => {
this.delete(this.list[0]);
}
//Remove and return max value
extractMax = () => {
const max = this.list[0];
this.delete(max);
return max;
}
//Size
size = () => this.list.length;
//IsEmpty
isEmpty = () => this.list.length === 0;
//Return head
getList = () => this.list;
}
Time complexity of heap data structure
| # | Access | Search | Insert | Delete | FindMax or (Min) | DeleteMax or (Min) |
|---|---|---|---|---|---|---|
| Average | Θ(N) | Θ(N) | ΘLog(N) | ΘLog(N) | Θ(1) | ΘLog(N) |
| Worst | O(N) | O(N) | OLog(N) | OLog(N) | O(1) | OLog(N) |
Space complexity
| # | space |
|---|---|
| Worst | O(N) |
Applications
- Implementing a priority queue.
- Dijkstra’s Algorithm.
- Heap Sort.