堆排序

#include <algorithm>
#include <iostream>
#include <vector>
#include <exception>

void sink(std::vector<int> &base, int i)
{
    int l = i * 2 + 1;
    int r = i * 2 + 2;
    if (base.size() <= l)
    {
        return;
    }
    if (base.size() <= r)
    {
        if (base[l] < base[i])
        {
            std::swap(base[l], base[i]);
        }
        return;
    }
    if (base[l] < base[r] && base[l] < base[i])
    {
        std::swap(base[l], base[i]);
        return sink(base, l);
    }
    if (base[r] < base[l] && base[r] < base[i])
    {
        std::swap(base[r], base[i]);
        return sink(base, r);
    }
}

void make_heap(std::vector<int> &base)
{
    for (int i = base.size() - 1; i >= 0; i--)
    {
        sink(base, i);
    }
}

int pop_heap(std::vector<int> &base)
{
    if (base.size() == 0)
    {
        throw std::runtime_error("");
    }
    int top = base.front();
    base.front() = base.back();
    base.pop_back();
    sink(base, 0);
    return top;
}

int main()
{
    std::vector<int> hp = {9, 2, 1, 4, 5, 6, 7};
    make_heap(hp);
    while (!hp.empty())
    {
        int i = pop_heap(hp);
        std::cout << i << ' ';
    }
    return 0;
}