手写二叉堆实现优先队列

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1123456];
//在数组 a 上维护大根堆
int len; //堆的大小 a[1]~a[len]
void up(int pos)
{
    int fa = pos / 2;
    if (pos == 1 || a[pos] < a[fa])
        return;
    swap(a[pos], a[fa]);
    up(fa);
}
void down(int pos)
{
    int lson = pos * 2;
    int rson = pos * 2 + 1;
    if (lson > len)
        return;
    int best = pos;
    if (lson <= len && a[lson] > a[best])
        best = lson;
    if (rson <= len && a[rson] > a[best])
        best = rson;
    if (best == pos)
        return;
    swap(a[pos], a[best]);
    down(best);
}
int main()
{
    cin >> n;
    len = 0;
    for (int i = 1; i <= n; i++)
    {
        int op, x;
        cin >> op >> x;
        if (op == 1)
        {
            //下面两行可以压成一行 a[++len] = x;
            len++;
            a[len] = x;
            up(len);
        }
        else if (op == 2)
        {
            cout << a[1] << "\n";
        }
        else if (op == 3)
        {
            swap(a[1], a[len]);
            len--;
            down(1);
        }
    }
    return 0;
}

std::priority_queue

基础使用方法

• priority_queue<int> q;，定义一个名字叫 q ，存 int 的优先队列
• q.size()，返回 q 里有多少个元素
• q.push(x)，把 x 压入 q
• q.top()，返回当前优先队列 q 中的最大值（堆顶），如果 q 是空的会出错
• q.pop()，弹出（删除）当前优先队列 q 中的最大值（堆顶），如果 q 是空的会出错
• q.empty()，如果优先队列 q 是空的就返回真，否则返回假

标程

#include <bits/stdc++.h>
using namespace std;
int n;
priority_queue<int> q;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int op, x;
        cin >> op >> x;
        if (op == 1)
            q.push(x);
        else if (op == 2)
            cout << q.top() << "\n";
        else if (op == 3)
            q.pop();
    }
    return 0;
}