Created
January 29, 2017 20:42
-
-
Save devteampentagon/89ccd601cafabc81fb4433a5adbd0e22 to your computer and use it in GitHub Desktop.
Heap Sort [Min 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 smallest 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 smaller | |
| if(l < n && arr[root] > arr[l]) | |
| root = l; | |
| // checking right child is within n and | |
| // either the right child is smaller | |
| if(r < n && arr[root] > arr[r]) | |
| root = r; | |
| // if root is the min value | |
| // then send it to the last sorted index | |
| // and as the current min 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 min 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 decreasing 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