Created
January 29, 2017 20:40
-
-
Save devteampentagon/2c736f3281cd75514ab617f5b167bda3 to your computer and use it in GitHub Desktop.
Heap Sort [Max Heap]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
#define MEM(a,b) memset((a),(b),sizeof(a)) | |
#define MAX(a,b) ((a)>(b)?(a):(b)) | |
#define MIN(a,b) ((a)<(b)?(a):(b)) | |
#define MIN3(a,b,c) MIN(MIN(a,b),c) | |
#define MIN4(a,b,c,d) MIN(MIN(MIN(a,b),c),d) | |
#define In freopen("In.txt", "r", stdin); | |
#define Out freopen("out.txt", "w", stdout); | |
#define i64 long long | |
#define u64 long long unsigned | |
#define INF (1<<28) | |
#define sz 100 | |
using namespace std; | |
int arr[sz]; | |
void heapify(int n, int i) | |
{ | |
int root, l, r; | |
root = i; // root is the largest value position | |
l = 2*i; // left child position | |
r = 2*i + 1; // right child position | |
// checking left child is within n and | |
// either the left child is greater | |
if(l < n && arr[root] < arr[l]) | |
root = l; | |
// checking right child is within n and | |
// either the right child is greater | |
if(r < n && arr[root] < arr[r]) | |
root = r; | |
// if root is the max value | |
// then send it to the last sorted index | |
// and as the current max value of 0 index is changed | |
// recursively checks to build heap again | |
if(root!=i) | |
{ | |
swap(arr[root],arr[i]); | |
heapify(n,root); | |
} | |
return; | |
} | |
void heapSort(int n) | |
{ | |
// building heaps | |
for(int i=n/2; i>=0; i--) | |
heapify(n,i); | |
// go for every elements | |
for(int i=n-1; i>0; i--) | |
{ | |
// swap the max element (first index) and | |
// the last index of unsorted | |
// data | |
swap(arr[0],arr[i]); | |
heapify(i,0); | |
} | |
return; | |
} | |
void printSortedArray(int n) | |
{ | |
// printing the sorted increasing list | |
for(int i=0; i<n; i++) | |
{ | |
if(i>0) cout << " "; | |
cout << arr[i]; | |
} | |
cout << endl; | |
return; | |
} | |
int main() | |
{ | |
int n; | |
while(cin >> n) | |
{ | |
for(int i=0; i<n; i++) | |
cin >> arr[i]; | |
heapSort(n); | |
printSortedArray(n); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment