题解 | 【模板】整数优先队列

C++ 通过最小堆（完全二叉树）来实现，O(log n)，（或者采用priority_queue

#include <array>
#include <iostream>
#include <type_traits>
#include <vector>
using namespace std;

// 完全二叉树 - 最小堆
class PriorityQueue {
    private:
    vector<unsigned int> heap; // 未知数组大小
    int size=0;
    void heapifUp(int idx) { // 插入：向上调整
        while (idx) {
            int parent = (idx-1)/2;
            if (heap[idx]>=heap[parent]) break;
            swap(heap[idx], heap[parent]);
            idx = parent;
        }
    }
    void heapifDown(int idx) { // 删除：向下调整
        while (true) {
            int left = 2*idx+1, right=left+1;
            int smallest = idx;
            if (left<size && heap[left] < heap[smallest]) smallest=left;
            if (right<size && heap[right] < heap[smallest]) smallest=right;
            if (smallest==idx) break;
            swap(heap[idx], heap[smallest]);
            idx = smallest;
        }
    }
    public:
    void enQueue(int x) {
        heap.push_back(x);
        heapifUp(size++);
    }
    void deQueue() {
        heap[0] = heap[--size]; // 最后一个元素移到堆顶
        heap.pop_back();
        heapifDown(0);
    }
    int peek() {
        return heap[0];
    }
    int getSize() {
        return size;
    }
};

int main() {
    int n, op;
    unsigned int x;
    cin >> n;
    PriorityQueue pq;
    while (n--) {
        cin >> op;
        switch (op) {
            case 1: cin >> x;  pq.enQueue(x); break;
            case 2: if (pq.getSize()) cout << pq.peek() << endl; break;
            case 3: if (pq.getSize()) pq.deQueue();break;
        }
    }
}
// 64 位输出请用 printf("%lld")

采用priority_queue

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

int main() {
    int n, op;
    unsigned int x;
    cin >> n;
    priority_queue<int, vector<int>, greater<>> pq;
    while (n--) {
        cin >> op;
        switch (op) {
            case 1: cin >> x;  pq.push(x); break;
            case 2: cout << pq.top() << endl; break;
            case 3: pq.pop();break;
        }
    }
}
// 64 位输出请用 printf("%lld")