堆

特点：

完全二叉树, 每个点都小于等于它的两个子节点(即集合中最小值为根节点)

堆的存储方式：

一维数组存储节点, 根节点下标为 1 . 如果该节点下标为 x , 那么该节点的左子节点的下标为 2x , 右子节点的下标为 2x + 1.

siz 表示当前堆的大小
heap 表示堆

cunchu

建堆方式：

在将一个集合建成堆的时候, 如果将每个数单独插入, 显然时间复杂度是 O(n \cdot logn) （每个点插入的时间与 down 耗时有关, 为 O(logn), 共有 n 个点, 则总时间复杂度为 $O(n \cdot logn)$

分析输入集合的性质即会发现, 输入数组本质就是一个乱序的完全二叉树, 我们要解决的问题就是将乱序排列为有序. 可以从 n / 2 即高度为 1 的位置开始遍历, 直到根节点结束

1	for (int i = n / 2; i; i --) down(i);

优化插入的时间复杂度分析：

对于每一个元素的插入, 时间复杂度均由 down 函数的时间复杂度 O(logn)决定.

在第一层 n / 2 共有 n / 4 个元素, down 最多的层数为 1 ；

在第二层 n / 4 共有 n / 8 个元素, down 最多的层数为 2 ；
即有公式：

shijianfuzadugongshi

对括号内的等比数列化简（错位相减）, 可以发现该部分小于 1 , 即总算法的时间复杂度为 O(n)

堆的基本操作：

下移节点 down (将该节点的值变大之后, 为维持堆的特性, 需要将该节点下移. 将该节点和该节点以及该节点的两个子节点中的最小值交换两个点, 重复该过程直到该节点大于等于该节点的父节点)

void down(int u) {
	int t = u;
	// t 表示当前节点和两个子节点中最小值的下标 
	if (u * 2 <= siz && h[u * 2] < h[t])
		t = u * 2; 
	if (u * 2 + 1 <= siz && h[u * 2 + 1] < h[t])
		t = u * 2 + 1;
    // 取出三个元素中的最小值的下标
	if (u != t) {
		swap(h[u], h[t]);
        // 交换
		down(t);
        // 递归操作, 直到元素满足条件
	}
}

上移节点 up (将该节点的值变小之后, 为维持堆的特性, 需要将该节点上移. 如果该节点小于该节点的父节点, 交换两个点, 重复该过程直到该节点大于等于该节点的父节点)

void up(int u) {
    while (u / 2 && h[u / 2] > h[u]) {
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}

堆支持的操作：

插入一个数
1
2
heap[++ siz] = x;
up(siz);
求集合当中的最小值
1
heap[1];

删除最小值

heap[1] = heap[siz --];
// 用最后一个点将第一个点覆盖
// 删除最后一个节点(siz --)
down(1);
// 将该点放到合适的位置

删除任意一个元素 k

1
2
3

heap[k] = heap[siz --];
down(1), up(1);
// 将新元素挪到合适的位置, 两个函数一个执行

修改任意一个元素 k
1
2
heap[k] = x;
down(k), up(k);

应用实例

1. 对顶堆

应用: 动态维护序列中位数

开一个大根堆和小根堆, 大根堆存储序列的前 $\lceil \frac{n}{2} \rceil$ 小的元素, 小根堆存储序列的后 $\lfloor \frac{n}{2} \rfloor$ 小元素, 大根堆对顶即为序列中位数.

向序列中插入元素 $x$ 时, 首先比较 $x$ 与小根堆对顶元素 $a$, 如果 $x \geq a$ 则插入小根堆, 否则插入大根堆. 最后根据两堆的 $\rm size$ 调整元素位置即可.

$Code$

if (qb.size() and a > qb.top()) qb.push(a), sb += a;
else qa.push(a), sa += a;
while (qb.size() < qa.size() + qb.size() >> 1) {
	qb.push(qa.top()), sb += qa.top();
	sa -= qa.top(), qa.pop();
}
while (qa.size() < qa.size() + qb.size() + 1 >> 1) {
	qa.push(qb.top()), sa += qb.top();
	sb -= qb.top(), qb.pop();
}

2. 可修堆

对于一个STL堆, 由于无法进行随即寻址, 也就不支持堆中元素的修改

我们可以使用两个堆, 一个堆记录删除元素, 另外一个堆记录增加元素, 弹出原堆元素时对原堆和删除堆堆顶元素进行比较, 会产生以下几种情况：

删除堆与插入的堆顶元素相等
此时表示原堆中的该数已经被删除, 该元素不可弹出
删除堆与插入堆堆顶元素不相等
此时表示当前元素未被修改, 该元素可弹出

Double Queue

3. 堆排序

太简单了, 每次取出数, 于是就不说了 $\sim$

堆 | 学习笔记

堆

特点：