binary_heap.cpp

#include <concepts>
#include <vector>
#include <cassert>
#include <iostream>

using namespace std;

template <typename T>
concept Comparable = requires (T a, T b) {
    {a < b} -> std::convertible_to<bool>;
    {a > b} -> std::convertible_to<bool>;
};

template <typename T>
concept RandomAccessable = requires (T param) { param[0]; };

template <typename T>
concept Heapable = RandomAccessable<T> && Comparable<decltype(T()[0])>;

template<Comparable T>
static bool compare(const T& a, const T& b) noexcept { return a > b; }

template<Heapable T>
static void heap_heapify_down(T& heap, int i, const int N) noexcept {
    while (true) {
        const int left = i * 2 + 1;
        const int right = i * 2 + 2;
        int smallest = i;
        if (left < N and compare(heap[smallest], heap[left])) smallest = left;
        if (right < N and compare(heap[smallest], heap[right])) smallest = right;
        if (i == smallest) break;
        swap(heap[smallest], heap[i]);
        i = smallest;
    }
}

template<Heapable T>
static void heap_heapify_up(T& heap, int i) noexcept {
    for (; i >= 0 and compare(heap[(i - 1) / 2], heap[i]); i = (i - 1) / 2) {
        swap(heap[(i - 1) / 2], heap[i]);
    }
}

template<Heapable T, Comparable U>
void heap_push(T& heap, const U& key) {
    heap.push_back(key);
    heap_heapify_up(heap, heap.size() - 1);
}

template<Heapable T, Comparable U>
void heap_update(T& heap, const int i, const U& key) noexcept {
    heap[i] = key;
    heap_heapify_up(heap, i);
    heap_heapify_down(heap, i, heap.size());
}

template<Heapable T>
void heap_pop(T& heap) noexcept {
    heap[0] = heap.back();
    heap.pop_back();
    heap_heapify_down(heap, 0, heap.size());
}

template<Heapable T>
void heap_make(T& heap) noexcept {
    for (int i = heap.size() / 2; i >= 0; --i) {
        heap_heapify_down(heap, i, heap.size());
    }
}

template<Heapable T>
void heap_sort(T& heap) noexcept {
    heap_make(heap);
    for (int i = heap.size() - 1; i >= 1; --i) {
        swap(heap[0], heap[i]);
        heap_heapify_down(heap, 0, i);
    }
    for (int i = 0; i < size(heap) / 2; ++i) {
        swap(heap[i], heap[size(heap) - i - 1]);
    }
}

template<Heapable T>
bool heap_isheap(const T& heap, const int idx) noexcept {
    if (idx >= size(heap)) return true;
    const int left = 2 * idx + 1;
    const int right = 2 * idx + 2;
    if (left < size(heap) and compare(heap[idx], heap[left])) return false;
    if (right < size(heap) and compare(heap[idx], heap[right])) return false;
    return heap_isheap(heap, left) and heap_isheap(heap, right);
}

int main() {
    static const auto DATA = vector{5, 3, 1, 2, 4, -2, -40, 100};
    static const auto DATA_SORTED = vector{-40, -2, 1, 2, 3, 4, 5, 100};

    const auto ConstructByPushing = [](const auto& data){
        auto pq = vector<int>();
        for (const int val : data) {
            heap_push(pq, val);
        }
        return pq;
    };

    const auto RemoveOneByOne = [](auto pq){
        vector<int> removed;
        while (not pq.empty()) {
            removed.push_back(pq[0]);
            heap_pop(pq);
        }
        return removed;
    };

    const auto ApplyHeapSort = [](auto pq){
        heap_sort(pq);
        return pq;
    };

    const auto ApplyMakeHeap = [](auto nums){
        heap_make(nums);
        return nums;
    };

    assert(heap_isheap(ConstructByPushing(DATA), 0));
    assert(RemoveOneByOne(ConstructByPushing(DATA)) == DATA_SORTED);
    assert(ApplyHeapSort(DATA) == DATA_SORTED);
    assert(heap_isheap(ApplyMakeHeap(DATA), 0));
    assert(RemoveOneByOne(ApplyMakeHeap(DATA)) == DATA_SORTED);
    cout << "OK" << endl;
}