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.

Min Heap

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.

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

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:

- 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.

// 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;}

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS