Heaps: Sort an Array using heap

Problem Statement:

Given an array, sort it by using heap sort.

Solution

Relationship between array and heap elements.

As we know that heaps are complete binary trees and they satisfy the below property:

If the parent node is stored at index I, the left child can be calculated by 2 * I + 1 and the right child by 2 * I + 2.

For a complete tree, the first index of a non-leaf node is given by (n/2-1) and all other nodes after that are leaf nodes and dont need to be heapified.

Heap Sort algorithm:

1. Build a max heap from the array,

2. Now the largest element will be at the root of the heap. Now replace with the last item of the heap and then heapify it again.

3. Repeat the step 2 till the size of heap is 1.

Solution in C++

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

using namespace std;

void heapify(int arr[], int n, int i) 
{
    // Find largest among root, left child and right child
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
      largest = left;

    if (right < n && arr[right] > arr[largest])
      largest = right;

    // Swap and continue heapifying if root is not largest
    if (largest != i) {
      swap(arr[i], arr[largest]);
      heapify(arr, n, largest);
    }
}

void heap_sort(int arr[], int n) 
{
    // build max heap
    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);

    // extrach the root element one by one
    for (int i = n - 1; i >= 0; i--) 
    {
        // move the root to the end
      swap(arr[0], arr[i]);

      // heapify again
      heapify(arr, i, 0);
    }
}

void print_array(int arr[], int n) 
{
    for (int i = 0; i < n; ++i)
      cout << arr[i] << " ";
    cout << "\n";
}

int main() 
{
    int arr[] = {3, 15, 12, 8, 9, 14};
    int n = sizeof(arr) / sizeof(arr[0]);
    heap_sort(arr, n);

    cout << "Sorted array is \n";
    print_array(arr, n);
}

Output:

Sorted array is
3 8 9 12 14 15