C++ Examples

C++ Program - Heap Sort

Heap sort uses property of heap to sort the array. It involves building a max heap for increasing order sorting which contains largest element of the heap at the root. For decreasing order sorting min heap is used which contains smallest element of the heap at the root. The process step of for increasing order sorting of heap sort is summarized below:

Step 1: Build a max heap which contains largest element of the heap at the root
Step 2: Swap the last element of heap with root element and remove the last element from the heap. With the remaining elements repeat the step 1.

Example:

To understand the heap sort, lets consider an unsorted array [10, 1, 23, 50, 7, -4] and discuss each step taken to sort the array in ascending order.

In the below figure, the heap structure of input array and max heap is shown. The index number of the root element of the heap is 0. In max heap, the largest element of the heap always resides at the root.

After building the initial max heap, the last element of heap is swapped with the root element and the last element which contains the largest number of the array is removed from the heap. After that, the heapify function is used on the remaining elements of the heap to make it as a max heap and the number of elements will reduce by one. This process is continued until the number of elements in the heap is one. At this point, the array will be sorted.

The above figure describes elimination of largest element from the heap and formation of the max heap from the remaining elements of the heap. The final outcome of the process is an increasing order sorted array.

Implementation of Heap Sort

#include <iostream>
using namespace std;

static void heapsort(int Array[], int n);
static void heapify(int Array[], int n, int i);
static void PrintArray(int Array[], int n);

// function for heap sort which calls heapify function 
// to build the max heap and then swap last element of 
// the max-heap with the first element
// exclude the last element from the heap and rebuild the heap
static void heapsort(int Array[], int n) {
  int temp;

  for(int i = n/2; i >= 0; i--) {
    heapify(Array, n-1, i);
  }
  
  for(int i = n - 1; i >= 0; i--) {
    //swap last element of the max-heap with the first element
    temp = Array[i];
    Array[i] = Array[0];
    Array[0] = temp;

    //exclude the last element from the heap and rebuild the heap 
    heapify(Array, i-1, 0);
  }
}

// heapify function is used to build the max heap
// max heap has maximum element at the root which means
// first element of the array will be maximum in max heap
static void heapify(int Array[], int n, int i) {
  int max = i;
  int left = 2*i + 1;
  int right = 2*i + 2;

  //if the left element is greater than root
  if(left <= n && Array[left] > Array[max]) {
    max = left;
  }

  //if the right element is greater than root
  if(right <= n && Array[right] > Array[max]) {
    max = right;
  }

  //if the max is not i
  if(max != i) {
    int temp = Array[i];
    Array[i] = Array[max];
    Array[max] = temp;
    //Recursively heapify the affected sub-tree
    heapify(Array, n, max); 
  }
}

// function to print array
static void PrintArray(int Array[], int n) { 
  for (int i=0; i<n; i++) 
    cout<<Array[i]<<" "; 
  cout<<"\n"; 
} 

// test the code
int main () {
  int MyArray[] = {10, 1, 23, 50, 7, -4};
  int n = sizeof(MyArray) / sizeof(MyArray[0]); 
  cout<<"Original Array\n";
  PrintArray(MyArray, n);

  heapsort(MyArray, n);
  cout<<"\nSorted Array\n";
  PrintArray(MyArray, n);
  return 0;
}

The above code will give the following output:

Original Array
10 1 23 50 7 -4 

Sorted Array
-4 1 7 10 23 50

Time Complexity:

The time complexity of creating a heap is Θ(N) and time complexity of creating a max heap is Θ(logN) and overall time complexity of heap sort is Θ(NlogN).

C++ Program - Heap Sort

Example:

Implementation of Heap Sort

Time Complexity:

Recommended Pages