优先队列的实现——堆

堆

堆的分类：

操作\数据结构	配对堆	二叉堆	左偏树	二项堆	斐波那契堆
插入（insert）	$O_{(1)}$	$O_{(\log_{n})}$	$O_{(\log_{n})}$	$O_{(1)}$	$O_{(1)}$
查询最小值（find-min）	$O_{(1)}$	$O_{(1)}$	$O_{(1)}$	$O_{(\log_{n})}$	$O_{(1)}$
删除最小值（delete-min）	$O_{(\log_{n})}$	$O_{(\log_{n})}$	$O_{(\log_{n})}$	$O_{(\log_{n})}$	$O_{(\log_{n})}$
合并 (merge)	$O_{(1)}$	$O_{(n)}$	$O_{(\log_{n})}$	$O_{(\log_{n})}$	$O_{(1)}$
减小一个元素的值 (decrease-key)	$O_{(\log_{n})}$ (上界 $\Omega_{\log\log_n}$ , 上界 $ O(2^{2{\sqrt {\log \log n}}})$)	$O_{(\log_{n})}$	$O_{(\log_{n})}$	$O_{(\log_{n})}$	$O_{(1)}$
是否支持可持久化	否	是	是	是	否

（表格引自OI-wiki | 看不懂的表格多了一个）

习惯上，不加限定的“堆”往往指二叉堆，这里也只讲二叉堆

二叉堆的基本性质：父节点永远不大于其子节点（大根堆）的完全二叉树（使用一维数组实现）

二叉堆的基本操作（STL提供）：

插入一个数
求集合中的最小/大值
删除最小/大值

二叉堆的进阶操作（STL不提供）：

删除任意元素
修改任意元素

二叉堆的原子操作（即以上五种操作都可由原子操作组合实现 | 大根堆为例）：

向上调整：待调整的节点与其父节点比较大小，若父节点小于子节点则交换父子节点位置；
向下调整：待调整节点与其子节点中最大的节点比较大小，若父节点小于子节点中最大的节点则交换两节点位置；
向上/向下调整的过程都是是与树的高度成正比的故时间复杂度都是 $O_{\log_n}$

实现：

插入一个数：
1. 在数组尾部插入一个数 heap[++size] = x
2. 对最后一个数向上调整以使得插入后任然满足堆的基本性质 up(size)
求集合中的最大值：
1. return heap[1]
删除最小/最大值：
1. 交换头结点和尾节点并删除尾部节点，即将尾节点的值覆盖头结点的值后删除尾节点 heap[1] = heap[size]; size--;
2. 将对新的尾节点向下调整 down(0)
删除任意位置的元素：
1. 交换K结点和尾节点并删除尾部节点，即将尾节点的值覆盖K结点的值后删除尾节点 heap[k] = heap[size]; size--;
2. 由于K节点与尾节点交换后可能变大也可能变小(尾节点不一定是值最小的点)，故有可能会向上调整也可能会向下调整，因此我们既向上调整一遍也向下调整一遍（只会执行其中一种调整） up(k); down(k);
修改任意一个数：
1. heap[k] = x
2. 向上和向下调整 up(k); down(k)
建堆：
1. 由于插入法建堆需要的复杂度是 $O_{n\log_n}$ ，那么有没有更好的办法建堆呢
2. 向上调整法：
  1
  2
  3
  void build_heap_1() {
  for (i = 1; i <= n; i++) up(i);
  }
  我们知道对于特定的k层节点向上调整的时间复杂度是 $O_{k}$ 的而不是 $O_{\log_n}$ 的
  
  故总的时间复杂度是 $\log_1 +2*\log_2+ ... +\frac{n}{2}\log_n$ 小于 $n\log_n$
  
  (吐槽一句，这样的建堆方式和插入建堆几乎一样，因为在最初插入元素较少时插入所需要调整的次数也很少，最终插入法建堆的复杂度总和也是和向上调整法建堆的计算方式是一致的)
3. 向下调整法：
  1
  2
  3
  void build_heap_2() {
  for (i = n>>1; i; i--) down(i);
  }
  由上面的向上调整法的启发我们很容易发现它的问题所在：要把上层节点数量较少需要向上调整调整的层数也少，而下层节点需要向上调整的层数明显较多而节点数目也更多这就导致大数乘大数时间复杂度无疑更大
  
  得到启发后，我们换一种方式让底层数量多的节点向下调整，这样经历的层数更少，而上层的节点向下调整时尽管经历的层数更多但同样的节点数目更少了，故感性的判断下这样的的调整方式的时间复杂度要更小，下面我们来算一下精确的时间复杂度
  
  $\begin{align*} &\frac{n}{2} \times 0 \ + \ \frac{n}{4} \times 1 \ + \ \frac{n}{8} \times 2 \ + \ ....\ + 1\times\log_n\\ \\ &=n\ (\frac{1}{2^2}\ +\ \frac{2}{2^3}\ +\ ...\ +\ \frac{\log_n}{n})\\\\ &令\ S\ =\ \frac{1}{2^2}\ +\ \frac{2}{2^3}\ +\ ...\ +\ \frac{\log_n}{n}\\\\ &则\ 2S\ =\ \frac{1}{2}\ +\ \frac{2}{2^2}\ +\ ...\ +\ \frac{\log_n}{n/2}\\\\ &故\ 2S-S\ =\ \frac{1}{2}\ +\ \frac{1}{2^2}\ +\ ...\\\\ &故\ S < 1\\\\ &\Rightarrow\ 原式 < n \\\\ \end{align*}$
  
  因此向下调整的时间复杂度是小于(约为) $O_{n}$
  
  之所以能 $O_{n}$ 建堆，是因为堆性质很弱，二叉堆并不是唯一的。
  
  要是像排序那样的强条件就难说了。

原子操作的核心代码：

void down(int u){
    int t = u;
    if(((u*2) <= size_heap) && h[u*2] < h[t]) t = u*2;
    if(((u*2)+1 <= size_heap) && h[(u*2)+1] < h[t]) t = (u*2)+1;
    if(u != t){
        swap(h[u], h[t]);
        down(t);
    }
}

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

tips：乘二除二这里可以改成移位操作

堆排序的完整代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 100010;

int n, m;
int h[N], size_heap;

void down(int u){
    int t = u;
    if(((u<<1) <= size_heap) && h[u<<1] < h[t]) t = u<<1;
    if(((u<<1)+1 <= size_heap) && h[(u<<1)+1] < h[t]) t = (u<<1)+1;
    if(u != t){
        swap(h[u], h[t]);
        down(t);
    }
}

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

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &h[i]);
    size_heap = n;
    
    for(int i = n>>1; i; i--) down(i);
    
    while(m--){
        printf("%d ", h[1]);
        h[1] = h[size_heap];
        size_heap--;
        down(1);
    }
    return 0;
}