Advertisement
HellFinger

Untitled

May 30th, 2019
201
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void heapify(int* arr, int n, int i)
  2. {
  3.     int largest = i; // Присваиваем наибольшему корень
  4.     int l = 2 * i + 1; // левый = 2*i + 1
  5.     int r = 2 * i + 2; // правый = 2*i + 2
  6.  
  7.     // Если левый больше корня
  8.     if (l < n && arr[l] > arr[largest])
  9.         largest = l;
  10.  
  11.     // Если левый больше корня
  12.     if (r < n && arr[r] > arr[largest])
  13.         largest = r;
  14.  
  15.     // Если больший не корень
  16.     if (largest != i)
  17.     {
  18.         swap(&arr[i], &arr[largest]);
  19.  
  20.         //Рекурсивно "хиппуем" поддерево от наибольшей величины
  21.         heapify(arr, n, largest);
  22.     }
  23. }
  24.  
  25. // главная функция для хип сорта
  26. void heapSort(int* arr, int n)
  27. {
  28.     // Строим кучу
  29.     for (int i = n / 2 - 1; i >= 0; i--)
  30.         heapify(arr, n, i);
  31.  
  32.     // Вытягиваем элементы по одному
  33.     for (int i = n - 1; i >= 0; i--)
  34.     {
  35.         // Меняем текущий корень в конец
  36.         swap(&arr[0], &arr[i]);
  37.  
  38.  
  39.         heapify(arr, i, 0);
  40.     }
  41. }
Advertisement
RAW Paste Data Copied
Advertisement