堆 | OI笔记

堆

特点：

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

堆的存储方式：

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

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

建堆方式：

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

分析输入集合的性质即会发现，输入数组本质就是一个乱序的完全二叉树，我们要解决的问题就是将乱序排列为有序。可以从 n / 2 即高度为 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 ；
即有公式：

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

堆的基本操作：

1. 下移节点 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);
        // 递归操作，直到元素满足条件
	}
}

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

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

堆支持的操作清单：

1. 插入一个数

   heap[++ siz] = x;
   up(siz);

2. 求集合当中的最小值

   heap[1];

3. 删除最小值

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

4. 删除任意一个元素 k

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

5. 修改任意一个元素 k

   heap[k] = x;
   down(k), up(k);

应用实例：

1. 对顶堆
   动态维护序列中位数
   Running Median

2. 可修改的堆

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

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

1. 删除堆与插入的堆顶元素相等
   此时表示原堆中的该数已经被删除，该元素不可弹出

2. 删除堆与插入堆堆顶元素不相等
   此时表示当前元素未被修改，该元素可弹出

Double Queue

3. 堆排序