Skip to content

Instantly share code, notes, and snippets.

@zarc1411
Created March 24, 2020 10:44
Show Gist options
  • Save zarc1411/b8218504f1bb3b98b2cf0375f76d9b45 to your computer and use it in GitHub Desktop.
Save zarc1411/b8218504f1bb3b98b2cf0375f76d9b45 to your computer and use it in GitHub Desktop.
/*
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment