Binary Heap | How to Implement in Javascript in 2022?

This article could be considered a complete guide on the binary heap. It contains the definition, its type, applications, and full implementation with an example.

Binary Heap

A binary heap is a tree data structure that has 2 properties  

• It should be a perfect binary tree (a.k.a structure-property)
• Each node of the tree should be either ≥ or ≤ than both of its children. In other words, It should be either Min heap or Max heap. (a.k.a heap property)

Perfect Binary Tree

A binary tree that is almost complete, the last level of the tree-filled from left to right.

e.g tree given in max heap and min heap is an example of a perfect binary tree

Note: if you have not read the binary tree before, please checkout

• How to implement binary tree in javascript?

• Top 5 Basic Must problems in the binary tree

Types of Binary Heap

It is of 2 types — 

1. Max Heap
2. Min Heap

Max Heap

A BH where each node of the tree is ≥ (greater than or equal to) than both of its children. Thus the root of the tree would be maximum among all of the nodes.

e.g below tree is an example of a Max heap

Min Heap

A BH where each node of the tree is ≤ (smaller than or equal to) than both of its children. Thus the root of the tree would be minimum among all of the nodes.

e.g below tree is an example of a Min heap

Representation of Binary Heap

A BH can be represented by the list of tree nodes as well by an Array. In this article, we will only focus on the Array representation of it.

Key points to note here are — 

• the root of the tree is arr[0]

• for any index i,

1. parent index = ( i – 1 ) / 2
2. left child index = 2 * i + 1
3. right child index = 2 * i + 2

Application of Heap

1. Heap Sort
2. Priority Queue
3. Graph Algorithms (Dijkstra— Shortest Path algorithm, Prims — MST)
4. Problems where you need to keep finding min after every iteration e.g

• Kth Largest element in the array
• Task Scheduler
• Maximum Product of 2 elements in an array

Here is the complete list  of problems on BH — Heap Problems

Binary Max Heap Implementation in Javascript

Usage

Approach 1: Insert the array elements one by one in the heap. Heap insert function calls function heapifyUp internally.

let pq = new BinaryMaxHeap();

let arr = [80,70,40,20,10,60,50,30];

for (let i = 0; i < arr.length; i++) {
    pq.insert(arr[i]);
}

console.log('Heap using approach 1', pq);

Approach 2: Insert complete array elements in the heap (by calling the build_heap function).

Heap function build_heap calls function heapify which heapify the whole heap.

let pr = new BinaryMaxHeap();

pr.build_heap(arr);

console.log('Heap using approach 2', pr);

Note:- Both Approaches results in the valid binary max heap. Resulting heap ordering could be same or different.

Result

Binary Min Heap Implementation in Javascript

Usage

Approach 1: Insert the array elements one by one in the heap. Heap insert function calls function heapifyUp internally.

let pq = new PriorityQueue();

let arr = [80,70,40,20,10,60,50,30];

for (let i = 0; i < arr.length; i++) {
    pq.insert(arr[i]);
}

console.log('Heap using approach 1', pq);

Approach 2: Insert complete array elements in the heap (by calling the build_heap function).

Heap function build_heap calls function heapify which heapify the whole heap.

let pr = new PriorityQueue();

pr.build_heap(arr);

console.log('Heap using approach 2', pr);

Note:- Both Approaches results in the valid binary min heap. Resulting heap ordering could be same or different.

Result

Summary

There are plenty of practical problems that will be solved easily by the binary heap data structure. It is a must one for all computer science grads.

In many programming languages, it is provided natively but knowing the core implementation and building a custom one is real learning.

The code in this article (which is written in javascript) can be imported to other programming languages of your choice.

Try to build it in the programming language you preferred.

Keep learning, and stay safe.