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.
Table of Contents
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
Types of Binary Heap
It is of 2 types —
- Max Heap
- 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,
- parent index = ( i – 1 ) / 2
- left child index = 2 * i + 1
- right child index = 2 * i + 2
Application of Heap
- Heap Sort
- Priority Queue
- Graph Algorithms (Dijkstra— Shortest Path algorithm, Prims — MST)
- Problems where you need to keep finding min after every iteration e.g
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.
Please share the articles on –
The latest tips and news from the industry straight to your inbox!
Join 30,000+ subscribers for exclusive access to our monthly news and tutorials!
