Coders Packet

Heap Sort in C++

By Timsal Zehra Rizvi

This Packet will provide a brief about the algorithm of heap Sort and how it is different from selection sort.

ABOUT:

Heap Sort is a comparison-based sorting algorithm that finds the largest element in the heap Data structure. Firstly a binary heap is built by rearranging the array, now the largest element (also the root node) is removed to store in an array recursively after every step, and the size of the heap is reduced. A detailed explanation of the implementation is given later in this article.

 

CODE:

#include 
using namespace std;

void buildMaxHeap(int arr[],int n,int i)
{
    int root = i;
    int child;
    while(root*2+1 < n ){
        child = root*2+1;
        if(child < n-1 && arr[child] < arr[child+1] )
        child= child +1;
        if(arr[root] < arr[child]){
            swap(arr[root], arr[child]);
            root = child;
        }
        else
        return ;
    }

}
 
void heapSort(int arr[], int n)
{
    int i=(n/2)-1;
    while(i>=0){
        buildMaxHeap(arr,n,i);
        i--;
    }
    int j=n-1;
    while(j>0){
        swap(arr[0],arr[j]);
        buildMaxHeap(arr,j,0);
        j--;
    }
}
 
int main()
{
    int size,i;
    cin>>size;
    int arr[size];
    for(i=0;i<size;i++)
    cin>>arr[i];
    heapSort(arr, size);
    cout << "OUTPUT:"<<endl;
    for(i=0;I<size;i++){
    cout<<arr[i]<<" ";
}

 

EXPLAINATION:

Step 1: Build a max heap from the array elements entered, here max heap refers to the binary heap data structure which follows a special order as the value of the parent node is greater than the values stored in the child nodes, So our first step would be to create a max heap to store the largest element as the root node. In the above code, we have created the function buildMaxHeap()  for the same reason.

Step 2: Swap the first element of the heap with the last element and simultaneously reduce the size of the heap, we have to recursively call the second step until the size of the heap built is greater than 1, see heapSort().

Step 3: Lastly, print the final array.

 

Note: 

#The Heap has to get updated after each removal 

#Max heap has to perform in a Bottom-up approach.

# The time complexity of the above algorithm is O(nlogn)

# Selection sort follows a linear time comparison of the unsorted region whereas heapsort builds max heap to find the largest element more quickly in each step, Selection Sort is an inline comparison based algorithm with time complexity O(n 2) therefore Heapsort can be regarded as an updated version of Selection Sort.



Hope this article helps you.

Download project

Reviews Report

Submitted by Timsal Zehra Rizvi (Zehra)

Download packets of source code on Coders Packet