Last Updated on December 14, 2022 by Prepbytes
What is Binary Heap?
A Binary Heap is a complete binary tree that follows a heap ordering property. The representation is done as:
Parent Node: (i-1)/2
Left Child: (2i) + 1
Right Child: (2i) + 2
The above table shows the indexes of the ith node.
Based on the Ordering property of binary heap, it can be of two types:
Min Heap: In Min heap, The value of the node is greater than or equal to the value of its parent’s node. The root node is the smallest in the min-heap.
For Example 1 : Using the above rules of array representation we can represent a heap in the array:
For node with value 2, its index value is 1 have left child is at (21) + 1 = 3 i.e. node with value 3 and right child is at (21) + 2 = 4 i.e. node with value 7. And we can see here that, both the children are bigger than their parent node.
For Example 2: Using the above rules of array representation we can represent a heap in the array:
For node with value 4, its index value is 2 have left child is at (22) + 1 = 5 i.e. node with value 16 and right child is at (22) + 2 = 6 i.e. node with value 18. And we can see here that, both the children are bigger than their parent node. Also its parent node will be at (2-1)/2 = 0 i.e. node with value 2.
Max Heap: In Max Heap, The value of the node is smaller than or equal to the value of its parent’s node. The root node is the greatest in max Heap.
For Example 1:
For node with value 6, its index value is 1 have left child is at (21) + 1 = 3 i.e. node with value 3 and right child is at (21) + 2 = 4 i.e. node with value 2. And we can see here that, both the children are bigger than their parent node.
For Example 2: Using the above rules of array representation we can represent a heap in the array:
For node with value 14, its index value is 2 have left child is at (22) + 1 = 5 i.e. node with value 6 and right child is at (22) + 2 = 6 i.e. node with value 8. And we can see here that, both the children are smaller than their parent node. Also its parent node will be at (2-1)/2 = 0 i.e. node with value 18.
This article tried to discuss the Array Representation of a Binary Heap. Hope this blog helps you understand the concept. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes