Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- int num[1000000];
- void sift(int *arr, int root, int bottom)
- {
- int maxChild;
- int done = 0;
- while ((root * 2 <= bottom) && (!done))
- {
- if (root * 2 == bottom)
- maxChild = root * 2;
- else
- if (arr[root * 2] > arr[root * 2 + 1])
- maxChild = root * 2;
- else
- maxChild = root * 2 + 1;
- if (arr[root] < arr[maxChild])
- {
- int curr = arr[root];
- arr[root] = arr[maxChild];
- arr[maxChild] = curr;
- root = maxChild;
- }
- else
- done = 1;
- }
- }
- void heapSort(int *arr, int arrlen)
- {
- for (int i = (arrlen / 2) - 1; i >= 0; i--)
- sift(arr, i, arrlen - 1);
- for (int i = arrlen - 1; i >= 1; i--)
- {
- int curr = arr[0];
- arr[0] = arr[i];
- arr[i] = curr;
- sift(arr, 0, i - 1);
- }
- }
- int main()
- {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int n;
- scanf("%d", &n);
- for (int i = 0; i < n; i++)
- scanf("%d", &num[i]);
- heapSort(num, n);
- for (int i = 0; i < n; i++)
- printf("%d ", num[i]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement