C++ Program To Heap Sort Using Dynamic Array

In this tutorial, we will see the heap sort algorithm that basically works on the heapify method.We can use two different approaches to heapsort either we acn use max heap or min heap,we will be using max heap here.Here firstly we need to create the max heap and then delete the parent node such that the resultant tree is also a max heap.

Befor moving towarsds the algorithm lets have a deep look on what exactly is a heap data structure.

Heap is a type of data structure that is based on trees. A priority queue is represented by a heap data structure. A binary tree is said to follow a heap data structure if:

• all nodes in the tree are greater than their children in the tree.
• It will be a complete binary tree.

Max-heap: - When each parent node is less than or equal to child nodes.

Min-heap: - When each parent node is greater than or equal to child nodes.

Let us consider some inputs to understand what should be the required output:

Input:

array: {2 3 9 7 1}

Output:

array: {1 2 3 7 9}

Input:

array: {56 9 11 7 60}

Output:

array: {7 9 11 56 60}

Heapsort Algorithm

As of now, we have a rough understanding of how heap sorting is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Define a function heapify()
2. Pass three parameters array, a and b
3. Find largest among root and children
4. If the root is not the largest, swap it with children
5. Continue to heapify
6. Define function Heap_Sort()
7. Pass array as a parameter
8. Build Max-heap and swap
9. Heapify the root element
10. The result will be the sorted array
11. Print the result

C++ Program for Heap Sort

#include <iostream>
  using namespace std;
  
  void heapify(int arr[], int n, int i) {
    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;
  
    if (largest != i) {
      swap(arr[i], arr[largest]);
      heapify(arr, n, largest);
    }
  }
  
  void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);
  
    // Heap sort
    for (int i = n - 1; i >= 0; i--) {
      swap(arr[0], arr[i]);
  
      heapify(arr, i, 0);
    }
  }
  

  void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
      cout << arr[i] << " ";
    cout << "\n";
  }
  
  int main() {
    int arr[] = {1, 12, 9, 5, 6, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
  
    cout << "Sorted array is \n";
    printArray(arr, n);
  }

Sorted array is
1 5 6 9 10 12

Conclusion

In this tutorial, we have performed a Heap Sort sort operation in C++ to sort an array. The heapsort algorithm doesn't have stability. The time complexity of the heapsort algorithm is O(n log n) and the space complexity is O(1).