二叉堆是一棵完全二叉树，树上每个节点都定义了一个权值，并且保证每个节点的权值都小于等于（或大于等于）其子节点的权值。为了区分，我们将权值大于等于子节点权值的堆称为大根堆，反之称为小根堆。

C++ STL 中的 priority_queue 实质上就是一个大根堆。

原理

存储

因为二叉堆是满二叉树，所以可以直接使用数组存储。从 1 开始存储时，节点 i 的左孩子下标为 2i，右孩子下标为 2i + 1。

于是存储只需在一个数组上储存数据，并维护堆大小（堆最大元素下标）即可。

以下使用结构体 HeapNode 代表一个堆节点。

const size_t MAXN = 1e5 + 5;
struct HeapNode {
    int data;
    friend bool operator<(HeapNode u, HeapNode v)
    {
        return u.data < v.data;
    }
} nodes[MAXN];
size_t n_nodes = 0;

操作

以下操作均以小根堆为例。

取最小元

显然堆顶就是最小元，直接返回即可。

HeapNode top()
{
    return nodes[1];
}

插入

插入时，直接将新节点插入到堆末尾。

这样做可能会破坏堆性质，所以插入后需要向上调整：将插入的节点与其父节点节点比较，若节点的权值比父节点小，则交换两个节点。重复以上操作，直至堆的序关系正确。

代码实现时，循环比较直至不等式成立或者 u 已经是堆顶即可。

void push(HeapNode node)
{
	n_nodes++;
	nodes[n_nodes] = node;
	// Push up
	for (size_t u = n_nodes; u != 1; u /= 2)
	{
		size_t v = u / 2;
		if (nodes[u] < nodes[v])
		{
			auto node = nodes[v];
			nodes[v] = nodes[u];
			nodes[u] = node;
		}
		else
		{
			return;
		}
	}
}

删除堆顶

删除堆顶时，类似于插入，首先交换堆顶与堆末节点，然后直接删除堆末尾节点即可。调整后的堆顶可能破坏了堆性质，所以需要向下调整。

向下调整：每次选择节点的两个子节点权值较大者，然后交换两个节点位置，直到堆的序性质已满足或者节点已经没有子节点。

实现时，因为可能出现堆有左子节点而没有右子节点的情况，先选出左、右子节点较大者（顺便判断右子节点是否存在），然后再比较原节点和选出的子节点。

void pop()
{
	nodes[1] = nodes[n];
	n--;

	// push down
	size_t u;
	for (u = 1; 2 * u <= n;)
	{
		size_t v = 2 * u;
		if (v + 1 <= n && nodes[v + 1] < nodes[v])
		{
			v++;
		}
		if (nodes[v] < nodes[u])
		{
			auto node = nodes[u];
			nodes[u] = nodes[v];
			nodes[v] = node;
			u = v;
		}
		else
		{
			return;
		}
	}
}

修改

在小根堆中，如果需要增加或减少一个节点的权重，直接修改节点即可。修改完后，如果增加了权重，则向下调整；如果减少了权重，则向上调整。

但已知值并不能直接寻找到堆节点，通常需要数组或 Hash 表辅助记录。

建堆

朴素的建堆可以选择逐个元素插入，复杂度是 O(n \log n)。但是，如果已知全部数据，还有更快速的 O(n) 建堆方法。

快速建堆的方法是：从堆的第 n 个节点，从后往前插入堆节点，同时逐个向下调整。这种情况下每个节点 i 至多向下调整 \log_2 n - \log_2 i 次，总操作次数为：

于是时间复杂度为 O(n)。

应用

离散事件模拟

使用小根堆存储事件和事件发生的时刻，每次取出下一个发生事件（即发生时刻最小的事件），这就是离散时间模拟（Discrete Event Simulation，DES）。

DES 问题非常适合使用优先队列存储，以时刻作为小根堆的排序依据，则小根堆每次取出的就是下一个事件；同时事件可能会导致新的事件产生，只需直接将新的事件插入小根堆即可。

例题：

• 2751. 机器人碰撞 - 力扣（LeetCode） ← 这题的最优实现不是 DES，但非常适合作为 DES 的练习题