专栏文章

题解：P3378 【模板】堆

GGs_The_Wolrd
P3378题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miph9dee
此快照首次捕获于
2025/12/03 11:58
3 个月前
此快照最后确认于
2025/12/03 11:58
3 个月前
查看原文

P3378 【模板】堆 题解

前置知识

什么是堆？

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

堆的操作

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

题目分析

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

Code

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

手写堆

手写堆理解起来有些困难，竞赛中经常不用。大佬轻喷。
CPP
#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;
}

优先队列

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

关于优先队列

优先队列定义
CPP
priority_queue<int,vector<int> > q; //小根堆
priority_queue<int,vector<int>, greater<int> > q; //大根堆
优先队列的内置函数
CPP
q.push(x); //插入     O(log n)
q.pop();   //弹出根   O(log n)
q.top();   //返回对顶元素 O(1)
q.size();  //返回长度     O(1)
那么这道题就很简单了，插入 push⁡\operatorname{push}，弹出 pop⁡\operatorname{pop}，返回栈顶 top⁡\operatorname{top}。
CPP
#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\log n，总时间复杂度 O(nlog⁡n)O(n\log n)。

其他

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

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...