HeapSort.cpp

/*
 Welcome!
  /\_/\  (
 ( ^.^ ) _)
   \"/  (
 ( | | )
(__d b__)
*/
#include<bits/stdc++.h>
using namespace std;

void maxHeapify(vector<int> &heap , int parentNodeIndex , int currentHeapSize)
{
    while(true)
    {
        int leftChildIndex = 2*parentNodeIndex + 1;
        int rightChildIndex = 2*parentNodeIndex + 2;
        int largestNodeIndex = parentNodeIndex;

        if(leftChildIndex<currentHeapSize && heap[leftChildIndex]>heap[parentNodeIndex])
        {
            largestNodeIndex = leftChildIndex;
        }
        if(rightChildIndex<currentHeapSize && heap[rightChildIndex]>heap[largestNodeIndex])
        {
            largestNodeIndex = rightChildIndex;
        }
        if(largestNodeIndex!=parentNodeIndex)
        {
            swap(heap[largestNodeIndex] , heap[parentNodeIndex]);
            parentNodeIndex = largestNodeIndex;
        }
        else
            break;
    }

}
void buildMaxHeap(vector<int> &heap , int currentHeapSize)
{
    for(int currentNodeIndex = (heap.size()/2) - 1 ; currentNodeIndex>=0 ; currentNodeIndex--)
    {
        maxHeapify(heap,currentNodeIndex , currentHeapSize);
    }
}
void heapSort(vector<int> &heap)
{
    int currentHeapSize = heap.size();
    buildMaxHeap(heap ,currentHeapSize);
    for(int currentNodeIndex = heap.size()-1 ; currentNodeIndex>=1 ; currentNodeIndex--)
    {
        swap(heap[0] , heap[currentNodeIndex]);
        currentHeapSize--;
        maxHeapify(heap , 0 , currentHeapSize);
    }
}
int main()
{
    vector<int> heap;
    int numberOfNodes = 0;
    cout<<"Enter the number of nodes\n";
    cin>>numberOfNodes;
    cout<<"Enter the value of nodes\n";
    for(int currentNodeIndex = 0 ; currentNodeIndex<numberOfNodes ; currentNodeIndex++)
    {
        int currentNodeValue = 0;
        cin>>currentNodeValue;
        heap.emplace_back(currentNodeValue);
    }
    heapSort(heap);
    cout<<"This is the sorted heap\n";
    for(int currentNodeIndex = 0 ; currentNodeIndex<numberOfNodes ; currentNodeIndex++)
    {
        cout<<heap[currentNodeIndex]<<" ";
    }

    return 0;
}