C++ program for heap sort

Last Updated on February 1, 2023 by Sumit Kumar

A heap is a complete binary tree, A complete binary tree is a binary tree in which all the levels are completely filled except the last level i.e. leaf node.

What is a Heap Sort Algorithm?

Heap Sort is a popular sorting Algorithm that processes the element by creating the min-heap or max-heap using the given array. Min-heap or max-heap represents the ordering of the array; the value of the root element will represent the minimum or maximum element of the array.
The basic concept of heap sort is to eliminate the elements one by one from the heap and then insert them in a sorted manner.

How to “heapify” a tree?

So, we can modify the tree in the max heap or min-heap. In other words, we can say, The reshaping of a binary tree into a heap tree is called heapify.

Algorithm:

• Build the max heap from the given array.
• After this, the largest element is stored at the top of the heap.
• Replace that element with the last element of the heap.
• Heapify the root of the tree.
• Repeat steps 3 and 4 while the size of the heap is greater than 1.

Working of Heap sort:

• In heap sort, there are two phases for sorting the elements. They are as follows:
• In the first step, we’ll create a heap by adjusting the elements of the array.
• After creating the heap, remove the root element repeatedly by swapping it with the last element of the array.

Now let’s see the working of heap sort in detail by using an example.

Code Implementation

#include <iostream>  
using namespace std;  
void heapify(int a[], int n, int i)  
{  
    int largest = i; 
    int left = 2 * i + 1;   
    int right = 2 * i + 2;   
  
    if (left < n && a[left] > a[largest])  
        largest = left;  

    if (right < n && a[right] > a[largest])  
        largest = right;  
    if (largest != i) {  
        int temp = a[i];  
        a[i] = a[largest];  
        a[largest] = temp;  
          
        heapify(a, n, largest);  
    }  
}  

void heapSort(int a[], int n)  
{  
  
    for (int i = n / 2 - 1; i >= 0; i--)  
        heapify(a, n, i);  
    for (int i = n - 1; i >= 0; i--) {  
        int temp = a[0];  
        a[0] = a[i];  
        a[i] = temp;  
          
        heapify(a, i, 0);  
    }  
}  

void printArr(int a[], int n)  
{  
    for (int i = 0; i < n; ++i)  
    {  
        cout<<a[i]<<" ";  
    }  
          
}  
int main()  
{  
    int a[] = {47, 9, 22, 42, 27, 25, 0};  
    int n = sizeof(a) / sizeof(a[0]);  
    cout<<"Before sorting array elements are - \n";  
    printArr(a, n);  
    heapSort(a, n);  
    cout<<"\nAfter sorting array elements are - \n";    
    printArr(a, n);  
    return 0;  
}  

Complexity

Time Complexity

Space Complexity – Constant O(1).

This article tried to discuss the Implementation of C++ program for Heap Sort. Hope this blog helps you understand the concept. To practice problems on Heap you can check out MYCODE | Competitive Programming – Heaps at Prepbytes

Other C++ Programs.

C++ Program to Add Two Numbers
C++ Program to Reverse a Number
Bubble Sort in C++ with Program Code and Example