Advertisement
Guest User

Untitled

a guest
Nov 21st, 2019
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.31 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int num[1000000];
  5.  
  6. void sift(int *arr, int root, int bottom)
  7. {
  8.     int maxChild;
  9.     int done = 0;
  10.    
  11.     while ((root * 2 <= bottom) && (!done))
  12.     {
  13.         if (root * 2 == bottom)
  14.             maxChild = root * 2;
  15.        
  16.         else
  17.             if (arr[root * 2] > arr[root * 2 + 1])
  18.                 maxChild = root * 2;
  19.         else
  20.             maxChild = root * 2 + 1;
  21.        
  22.         if (arr[root] < arr[maxChild])
  23.         {
  24.             int curr = arr[root];
  25.             arr[root] = arr[maxChild];
  26.             arr[maxChild] = curr;
  27.             root = maxChild;
  28.         }
  29.        
  30.         else
  31.             done = 1;
  32.     }
  33. }
  34.  
  35. void heapSort(int *arr, int arrlen)
  36. {
  37.     for (int i = (arrlen / 2) - 1; i >= 0; i--)
  38.         sift(arr, i, arrlen - 1);
  39.  
  40.     for (int i = arrlen - 1; i >= 1; i--)
  41.     {
  42.         int curr = arr[0];
  43.         arr[0] = arr[i];
  44.         arr[i] = curr;
  45.         sift(arr, 0, i - 1);
  46.     }
  47. }
  48.  
  49. int main()
  50. {
  51.     freopen("input.txt", "r", stdin);
  52.     freopen("output.txt", "w", stdout);
  53.    
  54.     int n;
  55.     scanf("%d", &n);
  56.    
  57.     for (int i = 0; i < n; i++)
  58.         scanf("%d", &num[i]);
  59.    
  60.     heapSort(num, n);
  61.    
  62.     for (int i = 0; i < n; i++)
  63.         printf("%d ", num[i]);
  64.        
  65.     return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement