Skip to main content

堆

参考资料​

简介​

堆（Heap）是一棵满足 堆序性质 的完全二叉树：每个节点的值都不小于（大根堆）或不大于（小根堆）其子节点。它支持 O(log⁡n)O(\log n) 插入与删除堆顶、O(1)O(1) 取最值，是优先队列的典型实现。OI 中通常直接用 STL 的 std::priority_queue，需要可并堆时再用左偏树。

std::priority_queue​

STL 的 std::priority_queue 默认是大根堆，传入 greater 比较器即为小根堆，是最常用的堆实现。

37 Bcpp
std::priority_queue<pair<int,int>> q;

__gnu_pbds::priority_queue​

__gnu_pbds::priority_queue 额外支持 O(log⁡n)O(\log n) 的堆合并与 O(1)O(1) 均摊的 modify、erase，可直接替代手写可并堆。

121 Bcpp
#include <bits/extc++.h>
using namespace __gnu_pbds;

__gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int>>> q;

左偏树​

左偏树（Leftist Tree）是一种可并堆，每个节点维护到最近外部节点的距离 dis\mathrm{dis} 并保持左子树的 dis\mathrm{dis} 不小于右子树，使两堆合并的复杂度为 O(log⁡n)O(\log n)。

273 Bcpp
struct Node
{
	int val,ls,rs,dis;
}t[N];
int merge(int x,int y)
{
	if(!x||!y)return x|y;
	if(t[x].val>t[y].val||(t[x].val==t[y].val&&x>y))swap(x,y);
	t[x].rs=merge(t[x].rs,y);
	if(t[t[x].ls].dis<t[t[x].rs].dis)swap(t[x].ls,t[x].rs);
	t[x].dis=t[t[x].rs].dis+1;
	return x;
}

例题​

洛谷 P3378 【模板】堆

给定一个数列，初始为空，请支持下面三种操作：

  1. 给定一个整数 xx，请将 xx 加入到数列中。
  2. 输出数列中最小的数。
  3. 删除数列中最小的数（如果有多个数最小，只删除 11 个）。
洛谷 P3377 【模板】左偏树/可并堆

有 nn 个小根堆，每个堆包含一个数。需要支持两种操作：

  1. 1 x y：将第 xx 个数和第 yy 个数所在的小根堆合并（若 xx 或 yy 已经被删除或 xx 和 yy 在同一个堆内，则无视此操作）。
  2. 2 x：输出第 xx 个数所在的堆最小数，并将这个最小数删除（若有多个最小数，优先删除先输入的；若第 xx 个数已经被删除，则输出 -1 并无视删除操作）。
洛谷 P11266 【模板】可并堆 2

给定正整数 nn 和 mm 以及一个长为 nn 的整数序列 a1,…,na_{1,\dots,n}。

你需要维护序列 a1,…,na_{1,\dots,n} 以及 nn 个集合 S1,…,nS_{1,\dots,n}，初始时 Si={ i }S_i=\set{i}。

接下来要进行以下四种操作共 mm 次，每次操作形如：

  • 0 x y：表示将元素 yy 从集合 SxS_x 中删去。保证此时元素 yy 在集合 SxS_x 中。
  • 1 x：表示询问 min⁡i∈Sxai\min_{i\in S_x} a_i，保证此时集合 SxS_x 非空。
  • 2 x y：将集合 SyS_y 中并入 SxS_x 并清空集合 SyS_y。保证此时集合 Sx,SyS_x,S_y 均非空，且此次操作后不会再出现涉及集合 SyS_y 的操作。
  • 3 x y z：表示将 aya_y 赋值为 zz。保证此时元素 yy 在集合 SxS_x 中，且 z<ayz<a_y。

不难发现这是一道堆的模板题，所以现在请你完成它。

洛谷 P2713 罗马游戏

有 nn 个士兵各带一个互异分数，初始各成一团。M i j 合并 i,ji,j 所在的团（若有一方已死则忽略）；K i 删除 ii 所在团中分数最小的士兵并输出其分数（若 ii 已死则输出 00）。

洛谷 P1456 Monkey King

有 NN 只猴子，各有一个强壮值。每次给出两只猴子，若已属同一群则输出 −1-1；否则两群各自最强壮的猴子决斗，强壮值减半（下取整），随后两群合并，输出合并后群中的最大强壮值。

洛谷 P10641 BZOJ3252 攻略

给定一个有 nn 个结点的树，树有点权且点权为正整数。现选取 kk 条从根结点出发到叶子结点的简单路径，求这些路径的并集上所有结点的点权之和的最大值。