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:

  1. 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.
  2. 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​.

%0 node_1 1 node_2 2 node_1->node_2 node_3 3 node_1->node_3 node_1594282014917 7 node_2->node_1594282014917 node_1594282070610 4 node_2->node_1594282070610 node_1594282132202 5 node_3->node_1594282132202 node_1594282135016 6 node_3->node_1594282135016
Min Heap
%0 node_1 15 node_2 12 node_1->node_2 node_3 13 node_1->node_3 node_1594282173234 7 node_2->node_1594282173234 node_1594282195659 8 node_2->node_1594282195659 node_1594282181243 5 node_3->node_1594282181243 node_1594282205794 10 node_3->node_1594282205794
Max 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.

Heapify
1 of 2

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 value 3 is 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:

  1. Parent node is index/2.
  2. Left child node is 2*index + 1.
  3. 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 heap
void heapify(int arr[], int i)
{
int smallest = i; // The node which will be heapified
int l = 2 * i + 1; // left child node
int r = 2 * i + 2; // right child node
// Check if left child is smaller than its parent
if (l < n && arr[l] < arr[smallest])
smallest = l;
// Check if right child is smaller than smallest
if (r < n && arr[r] < arr[smallest])
smallest = r;
// If smallest is not parent
if (smallest != i) {
swap(arr[i], arr[smallest]);
// Recursively heapify the affected sub-tree
heapify(arr, smallest);
}
}
// Function to build a Max-Heap from the given array
void buildHeap(int arr[])
{
// Perform level order traversal
// from last non-leaf node and heapify each node
for (int i = n; i >= 0; i--) {
heapify(arr, i);
}
}
// Driver Code
int main()
{
// Sample array
int arr[] = { 1, 5, 6, 8, 9, 7, 3};
// calculating size of array
n = 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 array
buildHeap(arr);
cout << "Array representation after buildHeap is: "<<endl;
// print the heap
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;
}
Copyright ©2024 Educative, Inc. All rights reserved