题解：P3378 【模板】堆

· · 题解

P3378 【模板】堆 题解

前置知识

什么是堆？

堆是一种树形结构，树的根在堆中就是堆顶，堆顶总是以你定义类型的最优值。堆有两种，一种是小根堆，堆顶是最小值。一种是大根堆，堆顶是最大值。

堆的操作

堆的操作有两种，上浮和下沉。顾名思义，上浮即为添加一个值后使其慢慢往上进行比较确认位置。下沉就是某个节点按优先级下降，或是替换堆顶的值。

题目分析

就是实现一个堆，有上浮，下沉，输出根三种操作。

Code

我这里提供两种写法，手写堆和 STL 中的优先队列。

手写堆

手写堆理解起来有些困难，竞赛中经常不用。大佬轻喷。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int n;
int q[maxn],len;           //len记录当前长度
int op,x;
void push(int x)           //插入新元素
{
    q[++ len] =x;
    int i = len;
    //上浮操作
    while(i > 1 && q[i] < q[i / 2]) 
    {
        swap(q[i],q[i / 2]);
        i /= 2;
    }
}
void pop() //下沉 删除堆顶
{
    q[1] = q[len --];
    int i = 1;
    while(2 * i <= len)
    {
        int ls = 2 * i; //左儿子 
        if(ls < len && q[ls + 1] < q[ls]) ls ++;
        if(q[ls] < q[i])
        {
            swap(q[ls],q[i]);
            i = ls;
        }
        else break;
    }
}
int main()
{
    scanf("%d",&n);
    while(n --)
    {
        scanf("%d",&op);
        if(op == 1) scanf("%d",&x),push(x);
        if(op == 2) printf("%d\n",q[1]);
        if(op == 3) pop();
    }
    return 0;
}

优先队列

优先队列底层基于堆，可以方便的插入和弹出。在竞赛中可用于优化代码。

关于优先队列

优先队列定义

priority_queue<int,vector<int> > q; //小根堆
priority_queue<int,vector<int>, greater<int> > q; //大根堆

优先队列的内置函数

q.push(x); //插入     O(log n)
q.pop();   //弹出根   O(log n)
q.top();   //返回对顶元素 O(1)
q.size();  //返回长度     O(1)

那么这道题就很简单了，插入 \operatorname{push}，弹出 \operatorname{pop}，返回栈顶 \operatorname{top}。

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>, greater<int> > q;
//priority_queue<int,vector<int> > q;
int n;
long long ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            int x;
            scanf("%d",&x);
            q.push(x); //插入
            continue;
        }
        else if(op==2)
        {
            printf("%d\n",q.top()); //输出
            continue;
        }
        else if(op==3)
        {
            q.pop(); //弹出
            continue;
        }
    }
    return 0;
}

不管是插入还是弹出的时间复杂度都是 \log n，总时间复杂度 O(n\log n)。

其他

刚刚提到了，优先队列可用于优化其他算法，例如 \operatorname{Dijstra}。可用优先队列找到当前点已有最短路最短的开始走。