Heap sort

heapSort.cc

#include <vector>

using namespace std;

void heap_sort(vector<int>& arr);
void build_heap(vector<int>& arr, int n);
void heapify(vector<int>& arr, int n, int root);

void heap_sort(vector<int>& arr) {
  build_heap(arr, arr.size());
  for (int i = arr.size() - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    heapify(arr, i, 0);
  }
}

void build_heap(vector<int>& arr, int n) {
  for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
}

void heapify(vector<int>& arr, int n, int root) {
  const int l = root * 2 + 1;
  const int r = root * 2 + 2;
  int _root = root;
  if (l < n && arr[_root] < arr[l]) _root = l;
  if (r < n && arr[_root] < arr[r]) _root = r;
  if (_root != root) {
    swap(arr[root], arr[_root]);
    heapify(arr, n, _root);
  }
}