算法 & 数据结构——优先队列

具备堆特性的队列，最大或最小的节点永远在第一个。

template <class T>
class PriorityQueue {
public:
    using Iter = typename std::vector<T>::iterator;

public:
    void Init()
    {
        for (auto i = _c.size() / 2; i != 0;)
        {
            Init(_c.begin(), --i, _c.size());
        }
    }

    void Push(const T & t)
    {
        _c.push_back(t);
        auto val = std::move(_c.back());
        auto idx = _c.end() - _c.begin();
        Push(_c.begin(), --idx, std::move(val));
    }

    void Pop()
    {
        auto len = _c.end() - _c.begin();
        std::swap(_c.front(), _c.back());
        Init(_c.begin(), 0, len - 1);
        _c.pop_back();
    }

    T & Top()
    {
        return _c.front();
    }

    bool Empty()
    {
        return _c.empty();
    }

    size_t Length()
    {
        return _c.size();
    }

    const std::vector<T> & Get()
    {
        return _c;
    }

    void Sort()
    {
        for (auto i = _c.size(); i != 0;)
        {
            --i;
            std::swap(_c.at(0), _c.at(i));
            Init(_c.begin(), 0, i);
        }
    }

private:
    void Init(Iter first, size_t idx, size_t len)
    {
        if (idx < len / 2)
        {
            auto max = idx;
            auto l = idx * 2 + 1;
            auto r = idx * 2 + 2;
            if (l < len && *(first + max) < *(first + l))
            {
                max = l;
            }
            if (r < len && *(first + max) < *(first + r))
            {
                max = r;
            }
            if (max != idx)
            {
                std::swap(  *(first + idx), 
                            *(first + max));
                Init(first, max, len);
            }
        }
    }
    
    void Push(Iter first, size_t idx, T && val)
    {
        for (auto   par = (idx - 1) / 2;
                    idx > 0 && *(first + par) < val;
                    par = (idx - 1) / 2)
        {
            *(first + idx) = std::move(*(first + par));
            idx = par;
        }
        *(first + idx) = std::move(val);
    }
    
private:
    std::vector<T> _c;
};

当Push被调用时，新增的节点会通过<运算符放置在合适的位置
当Pop被调用时，弹出队列元素，并且调整堆。