How to build a heap from an array
A heap is a binary tree that satisfies the heap property. Heap can be of two types:
- Min heap: The element of each node is greater than or equal to the element at its parent. The minimum value element is at the root.
- Max heap: The element of each node is less than the element at its parent. The maximum value element is at the root.
Through this shot, the word “heap” will always refer to min-heap.
In a heap the min (or max) priority element is always stored at the root; hence, the name “heap”. A heap is not a sorted structure and can be regarded as partially ordered. As you can see from the images above, there is no discrete order between the nodes at any level.
A heap is useful when you need to remove the object with the minimum (or maximum) priority. A common use of a heap is to implement a priority queue.
Building heap from an array
If, for example, you wanted to build a min-heap using an array, the element at the child node should always be greater than the element at the parent node.
For an array implementation in heaps, the index starts from 1, not 0. The first index represents a value “root”, which is why it is kept empty. In the example above, the heap constructed for the array
arr = [1,5,6,8,9,7,3]violates the heap order property as the value3is not greater than the element at its parent node (6). Therefore, in order to maintain heap property, they are swapped.
Building a heap from array makes sure that heap order property is maintained after every input. The input is checked if it is greater than it’s parent, if it’s not, it is swapped.
In an array, the element at each node occupies an index in the array. For example, a node containing element 6 occupies index = 3 in the array. Similarly, a node containing element 9 occupies index=5 in the array. For any given node, there are three properties to remember:
- Parent node is index/2.
- Left child node is 2*index + 1.
- Right child node is 2*index + 2.
For example, a node containing element 6 occupies index = 3 in the array. Therefore, since parent = index/2 (means the parent of element 6 has index =1 in the array), it has the value of 1. The index values for the left and right nodes can be similarly calculated.
Code
// C++ program for building Heap from Array#include <iostream>using namespace std;int n; // size of array// To heapify a subtree rooted with node i which is// an index in arr[]. N is size of heap// we are using an array to create min heapvoid heapify(int arr[], int i){int smallest = i; // The node which will be heapifiedint l = 2 * i + 1; // left child nodeint r = 2 * i + 2; // right child node// Check if left child is smaller than its parentif (l < n && arr[l] < arr[smallest])smallest = l;// Check if right child is smaller than smallestif (r < n && arr[r] < arr[smallest])smallest = r;// If smallest is not parentif (smallest != i) {swap(arr[i], arr[smallest]);// Recursively heapify the affected sub-treeheapify(arr, smallest);}}// Function to build a Max-Heap from the given arrayvoid buildHeap(int arr[]){// Perform level order traversal// from last non-leaf node and heapify each nodefor (int i = n; i >= 0; i--) {heapify(arr, i);}}// Driver Codeint main(){// Sample arrayint arr[] = { 1, 5, 6, 8, 9, 7, 3};// calculating size of arrayn = sizeof(arr) / sizeof(arr[0]);cout << "Array representation before buildHeap is: "<<endl;for (int i = 0; i < n; ++i)cout << arr[i] << " ";cout <<endl;// call the buildheap method on the arraybuildHeap(arr);cout << "Array representation after buildHeap is: "<<endl;// print the heapfor (int i = 0; i < n; ++i)cout << arr[i] << " ";return 0;}
Free Resources
