A binary Heap is a special kind of tree. For a Binary Tree to be a Binary Heap the rule is simple-
As we can see, there are 2 types of Binary Heap- min and max.
NOTE
In this article, we are discussing the implementation of Binary Heap(both Min and Max) in JavaScript and TypeScript.
Max Binary Heap
If we represent this Heap(binary tree) in an array, it will look like below-
Notice the indexes of the elements. Here can find the index of child elements from the index of parent, can find parent from the index of children, using the following formula-
- If the parent element is in N th index, then-
- Left child index: 2N + 1
- Right child index: 2N + 2
- If the child element is in N th index, then-
- Parent element index: floor((N – 1) / 2)
Step #1: MaxBinaryHeap Class
Step #2: Insert Method
Step #3: Heapify Utility Method
Step #2: Extract Max Method
Full Source Code
Demo
Output:
----------- Max Binary Heap - Insert example -----------
Insert - 190| Result: [ 190 ]
Insert - 100| Result: [ 190, 100 ]
Insert - 120| Result: [ 190, 100, 120 ]
Insert - 150| Result: [ 190, 150, 120, 100 ]
Insert - 80| Result: [ 190, 150, 120, 100, 80 ]
Insert - 110| Result: [ 190, 150, 120, 100, 80, 110 ]
Insert - 40| Result: [
190, 150, 120,
100, 80, 110,
40
]
Insert - 10| Result: [
190, 150, 120, 100,
80, 110, 40, 10
]
Insert - 55| Result: [
190, 150, 120, 100,
80, 110, 40, 10,
55
]
Insert - 60| Result: [
190, 150, 120, 100,
80, 110, 40, 10,
55, 60
]
----------- Max Binary Heap - Extract max example example -----------
Extract root | Result: 190
Extract root | Result: 150
Extract root | Result: 120
Extract root | Result: 110
Extract root | Result: 100
Extract root | Result: 80
Extract root | Result: 60
Extract root | Result: 55
Extract root | Result: 40
Extract root | Result: 10
Extract root | Result: undefined
Extract root | Result: undefinedTesting
Time Complexity
| Operation | Complexity |
|---|---|
| Insert | O(log N) |
| Extract Max | O(log N) |
Min Binary Heap
If we represent this Heap(binary tree) in an array, it will look like below-
Notice the indexes of the elements. Here can find the index of child elements from the index of parent, can find parent from the index of children, using the following formula-
- If parent element is in N th index, then-
- Left child index: 2N + 1
- Right child index: 2N + 2
- If child element is in N th index, then-
- Parent element index: floor((N – 1) / 2)
Step #1: MinBinaryHeap Class
Step #2: Insert Method
Step #3: Heapify Utility Method
Step #2: Extract Min Method
Full Source Code
Demo
Output:
----------- Min Binary Heap - Insert example -----------
Insert - 10| Result: [ 10 ]
Insert - 40| Result: [ 10, 40 ]
Insert - 60| Result: [ 10, 40, 60 ]
Insert - 55| Result: [ 10, 40, 60, 55 ]
Insert - 80| Result: [ 10, 40, 60, 55, 80 ]
Insert - 110| Result: [ 10, 40, 60, 55, 80, 110 ]
Insert - 150| Result: [
10, 40, 60, 55,
80, 110, 150
]
Insert - 100| Result: [
10, 40, 60, 55,
80, 110, 150, 100
]
Insert - 120| Result: [
10, 40, 60, 55,
80, 110, 150, 100,
120
]
Insert - 190| Result: [
10, 40, 60, 55,
80, 110, 150, 100,
120, 190
]
----------- Min Binary Heap - Extract max example -----------
Extract root | Result: 10
Extract root | Result: 40
Extract root | Result: 55
Extract root | Result: 60
Extract root | Result: 80
Extract root | Result: 100
Extract root | Result: 110
Extract root | Result: 120
Extract root | Result: 150
Extract root | Result: 190
Extract root | Result: undefined
Extract root | Result: undefinedTesting
Time Complexity
| Operation | Complexity |
|---|---|
| Insert | O(log N) |
| Extract Min | O(log N) |
Source Code
Use the following links to get the source code used in this article-
| Source Code of | Implementation Code | Demo Code | Test Code |
|---|---|---|---|
| JavaScript Implementation |  GitHub | GitHub | GitHub |
| TypeScript Implementation | GitHub | GitHub | GitHub |
Related Data Structures
| Command | Details |
|---|---|
| Singly Linked List | Singly Linked List Detail |
Other Code Implementations
Use the following links to check the BFS implementation in other programming languages-
