Heaps: Build Min Heap from an Array

Problem Statement:

You are given N array elements.
You need to build a Min Heap.

Solution

Min Heap: The root element is greater than its children.

In this approach, we will heapify for every element inserted.

Changing the structure of the heap to meet the heap property is called as heapify.

Heap Property:

Left child of i-th node is at (2*i + 1)th index.
Right child of i-th node is at (2*i + 2)th index.
Parent of i-th node is at (i-1)/2 index.

To heapify a single node takes O(log N) for N total number of Nodes it will take O(N*logN).

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 

using namespace std;

void heapify(int arr[], int i, int len) 
{ 
    int smallest = i; // node to 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 < len && arr[l] < arr[smallest]) 
        smallest = l; 

    // Check if right child is smaller than smallest 
    if (r < len && 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, len); 
    } 
} 

void build_min_heap(int arr[], int len) 
{
    // perform level order traversal from non leaf node
    for (int i = len; i >= 0; i--) { 
        heapify(arr, i, len); 
    } 
} 

int main() 
{ 
    int arr[] = { 1, 5, 6, 8, 9, 7, 3}; 
    int len = sizeof(arr) / sizeof(arr[0]); 

    cout << "Current array"<<endl; 

    for (int i = 0; i < len; ++i) 
        cout << arr[i] << " ";

    cout <<endl; 

    build_min_heap(arr, len); 

    cout << "After heapify "<<endl; 

    for (int i = 0; i < len; ++i) 
        cout << arr[i] << " "; 

    return 0; 
}

Output:

Current array
1 5 6 8 9 7 3

After heapify
1 5 3 8 9 7 6