题解 | #【模板】堆#

将数组heap看成完全二叉树，用heap的索引按层序给完全二叉树编号，编号为i的节点的值对应heap[i]的值，那么二叉树的根、左、右节点编号满足left=2root+1,right=2root+2，按照这个规则访问数组就像在访问二叉树，再将二叉树构建成所有根节点都大于等于左右子节点。

#include<iostream>
#include<string>
using namespace std;

template <typename T>
class myHeap
{
private:
    vector<T> heap;
    void swap(T &a, T &b)
    {
        T tmp = a;
        a = b;
        b = tmp;
    }
    // pop后向下递归调整 最差O(logn)
    void down_adjust(int root)
    {
        int left = 2 * root + 1;
        int right = 2 * root + 2;
        int largest = root;
        //找到根、左、右中最大值的索引
        if (left < heap.size() && heap[left] > heap[largest])
            largest = left;
        if (right < heap.size() && heap[right] > heap[largest])
            largest = right;
        if (largest != root)
        {
            swap(heap[largest], heap[root]);
            down_adjust(largest); //继续递归调整左子节点或者右子节点
        }
    }
    // push后向上调整 最差O(logn)
    void up_adjust()
    {
        int last = heap.size() - 1; //最后一个节点
        int root = (last - 1) / 2;  //最后一个节点的父节点
        // push的元素被调整到堆顶或者小于等于根时退出循环
        while (root >= 0 && heap[last] > heap[root])
        {
            swap(heap[last], heap[root]);
            last = root;
            root = (root - 1) / 2;           
        }
    }
    //从数组构建堆O(n)
    void construct()
    {
        //从最后一个根节点开始调整
        for (int i = (heap.size() - 2) / 2; i >= 0; i--)
        {
            down_adjust(i);
        }
    }

public:
    void push(T val)
    {
        heap.push_back(val);
        up_adjust();
    }
    T pop()
    {
        T tmp = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        down_adjust(0);
        return tmp;
    }
    T top()
    {
        return heap[0];
    }
    bool empty()
    {
        return heap.size() == 0;
    }
};

int main()
{
    int n;
    cin >> n;
    string opt;
    int val;
    myHeap<int> mh;
    for (int i = 0; i < n; i++)
    {
        cin>>opt;
        if(opt=="push"){
            cin >> val;
            mh.push(val);
        }
        else if(opt=="pop"){
            if(mh.empty())
                cout << "empty" << endl;
            else
                cout << mh.pop() << endl;
        }
        else{
            if(mh.empty())
                cout << "empty" << endl;
            else
                cout << mh.top() << endl;
        }
    }
}