SortHeap.cc

#include <format>
#include <iostream>
#include <random>
#include <span>

#include "vector.hh"

/**
 *   (k-1)/2
 *      |
 *      k
 *    /   \
 *  2k+1  2k+2
 */

template <typename compar>
struct heap {
  static void sort(std::span<compar> pq) {
    int n = pq.size() - 1;
    // heapify phase
    for (int k = (n - 1) / 2; k >= 0; --k) sink(pq, k, n);
    // sortdown phase
    while (n > 0) {
      std::swap(pq[0], pq[n--]);
      sink(pq, 0, n);
    }
  }

  static void sink(std::span<compar> pq, int k, int n) {
    while (2 * k + 1 <= n) {
      int j{2 * k + 1};
      if (j < n && pq[j] < pq[j + 1]) ++j;
      if (pq[k] >= pq[j]) break;
      std::swap(pq[k], pq[j]);
      k = j;
    }
  }
};

int main() {
  std::mt19937 mt(std::random_device{}());
  std::uniform_int_distribution rand(10, 99);

  ns::vector<int> A(16);
  for (auto &e : A) {
    e = rand(mt);
    std::cout << e << '\t';
  }
  std::cout << "\n\n";

  heap<int>::sort(A);
  std::ranges::for_each(A, [](auto x) { std::cout << x << '\t'; });
  std::cout << "\n\n";

  std::cout << std::format("{}",
                           std::ranges::is_sorted(A) ? "Sorted" : "Unsorted");
  std::cout << '\n';
}