题解 | #【模板】堆#

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class MaxHeap {
  public:
    MaxHeap(): heapSize(0) {};
    void push(int x) {
        // nums.push_back(x);
        pque.push(x);
        heapSize++;
        // heapify_up(heapSize - 1);
    };
    int top() {
        if (pque.size() == 0) return -1;
        // return nums[0];
        return pque.top();
    };
    void pop() {
        if (pque.size() == 0) {
            cout << "empty" << endl;
            return;
        }
        cout << pque.top() << endl;
        pque.pop();
        // swap(nums[0], nums[heapSize - 1]);
        // heapSize--;
        // heapify_down(0);
    };
  private:
    vector<int> nums;
    int heapSize;
    function<bool(int,int)> cmp= [](int a,int b){
        return a<b;
    };
    priority_queue<int,vector<int>,function<bool(int,int)>> pque{cmp};
    void heapify_up(int i) {
        int parent = (i - 1) / 2;
        while (parent >= 0) {
            heapify_down(parent);
            parent--;
        }
    }
    void heapify_down(int i) {
        int largest = i;
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        if (left < heapSize && nums[largest] < nums[left]) largest = left;
        if (right < heapSize && nums[largest] < nums[right]) largest = right;
        if (largest != i) {
            swap(nums[largest], nums[i]);
            heapify_down(largest);
        }
    }
};


int main() {
    MaxHeap p;
    int n, a;
    cin >> n;
    string op;
    while (cin >> op) {
        if (op == "push") {
            cin >> a;
            p.push(a);
        } else if (op == "top") {
            int x = p.top();
            if (x != -1)
                cout << x << endl;
            else cout << "empty" << endl;
        } else if (op == "pop") {
            p.pop();
        }
    }
}
// 64 位输出请用 printf("%lld")