Advertisement
Araf_12

Heap Sort

Feb 14th, 2023 (edited)
26
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.59 KB | None | 0 0
  1. void heapify(vector<int>& arr, int n, int i) {
  2.     int largest = i;
  3.     int l = 2 * i + 1;
  4.     int r = 2 * i + 2;
  5.  
  6.     if (l < n && arr[l] > arr[largest])
  7.         largest = l;
  8.  
  9.     if (r < n && arr[r] > arr[largest])
  10.         largest = r;
  11.  
  12.     if (largest != i) {
  13.         swap(arr[i], arr[largest]);
  14.         heapify(arr, n, largest);
  15.     }
  16. }
  17.  
  18. void heapSort(vector<int>& arr) {
  19.     int n = arr.size();
  20.  
  21.     for (int i = n / 2 - 1; i >= 0; i--)
  22.         heapify(arr, n, i);
  23.  
  24.     for (int i = n - 1; i > 0; i--) {
  25.         swap(arr[0], arr[i]);
  26.         heapify(arr, i, 0);
  27.     }
  28. }
  29.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement