Question

Illustrate the HeapSort on the following array. [ 7, 2, 4, 6, 3, 1, 5 ] Show the array and the heap after each call to ReHeap.

Answer 1

C++ program for implementation of Heap Sort :

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
   int largest = i; // Initialize largest as root
   int l = 2 * i + 1; // left = 2*i + 1
   int r = 2 * i + 2; // right = 2*i + 2

   // If left child is larger than root
   if (l < n && arr[l] > arr[largest])
       largest = l;

   // If right child is larger than largest so far
   if (r < n && arr[r] > arr[largest])
       largest = r;

   // If largest is not root
   if (largest != i) {
       swap(arr[i], arr[largest]);

       // Recursively heapify the affected sub-tree
       heapify(arr, n, largest);
   }
}

// main function to do heap sort
void heapSort(int arr[], int n)
{
   // Build heap (rearrange array)
   for (int i = n / 2 - 1; i >= 0; i--)
       heapify(arr, n, i);

   // One by one extract an element from heap
   for (int i = n - 1; i >= 0; i--) {
       // Move current root to end
       swap(arr[0], arr[i]);

       // call max heapify on the reduced heap
       heapify(arr, i, 0);
   }
}

/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
   for (int i = 0; i < n; ++i)
       cout << arr[i] << " ";
   cout << "\n";
}
void print(const int &i) {
   std::cout << i << ' ';
}

int main()
{
   int arr[] = { 7, 2, 4, 6, 3, 1, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);

   cout << "Given Array List Before HeapSort: \n";

std::for_each(std::begin(arr), std::end(arr), print);

cout<< "\n";

   heapSort(arr, n);
   cout << "Sorted array After HeapSort: \n";
   printArray(arr, n);

return 0;
}

Output:

Given Array List Before HeapSort: 
7 2 4 6 3 1 5 
Sorted array After HeapSort: 
1 2 3 4 5 6 7 

==================================================================

Code Snap Pictures:

Output:

Please give Thumbsup....