DSA - 优先级队列 + 习题集

发表于 2026-06-19 分类于数据结构阅读次数：本文字数： 1.9k 阅读时长 ≈ 7 分钟

我的天呐我真的爱死迷宫饭了。

这是习题集和笔记的合体，边看习题集边做笔记的。

完全二叉堆

逻辑上是二叉树，物理上是向量。

大顶堆处处满足 H [i]<=H [parent (i)]，小顶堆相反。于是没父亲的就是最大元素。

插入

先插入到向量末尾再上滤。

上滤：自底向上，发现父不如子就调换。

0001 template <typename T> void PQ_ComplHeap<T>::insert( T e ) {
0002    Vector<T>::insert( e ); //将新词条接至向量末尾
0003    percolateUp( _elem, _size - 1 ); //再对该词条上滤调整
0004 } //insert

0001 template <typename T> Rank percolateUp( T* A, Rank i ) { //0 <= i < _size
0002    for ( Rank j; (0 < i) && (A[j = Parent(i)] < A[i]); i = j ) //自下而上，逐层检视
0003       swap( A[i], A[j] ); //只要父不如子，随即易位
0004    return i; //返回最终抵达的位置
0005 } //percolateUp

祖先不超过 logn 个，于是 O (logn)

每次把上滤元素拿手里，如果能上滤就把父亲向下覆盖，直到不能再往上走了用上滤元素覆盖当前位置。

$X 是发生交换的次数，E (x)=\sum_{k = 1}^{h {P (X>=k)}$，能上滤 k 次说明 x 比这个子树所有元素都要大，P (X>=k)=1 / Nk，而 Nk 对应子树差不多高度是 k，差不多有 2}k 个元素，求和差不多是 1

删除

把堆顶和堆末尾元素调换，–size 表示堆底 - 1 也就是删除了原先的堆顶。

这时候需要下滤，把现在的堆顶往下移动。每次检视自己和两个儿子，如果有儿子比自己大就选择最大的儿子来和自己调换，从上到下不断审视路径上的节点直到当前位置不需要调换。

0001 template <typename T> T PQ_ComplHeap<T>::delMax() {
0002    swap( _elem[0], _elem[--_size] ); //堆顶、堆尾互换（不致引发shrink()）
0003    percolateDown( _elem, _size, 0 ); //新堆顶下滤
0004    return _elem[_size]; //返回原堆顶
0005 } //delMax
0001 template <typename T> Rank percolateDown( T* A, Rank n, Rank i ) { //0 <= i < _size
0002    for ( Rank j; i != ( j = ProperParent( A, n, i ) ); i = j ) //自上而下，逐层检视
0003       swap( A[i], A[j] ); //只要i不堪为父，随即与更强的孩子j易位
0004    return i; //返回最终抵达的位置（亦i亦j）
0005 } //percolateDown

记 X 为下滤次数，Y 是最后停在的层数，那么 X=h-Y。E (Y) 推导类似上面，如果停在第 Y 层说明比所有后代都大，概率 Nk，计算出来也是 1。而 h-1=logn-1=O (logn)，依旧 logn。

建堆

自然有挨个都上滤一遍的 O (nlogn) 的做法。

Floyd 建堆：

注意是先从底部开始，先从建立小堆再把小堆合起来变成大堆。

0001 template <typename T> void heapify( T* A, const Rank n ) { //Floyd建堆算法，O(n)时间
0002    for ( Rank i = n / 2 - 1; - 1 != i; i-- ) //按照层次遍历的逆序，逐个地
0003       percolateDown( A, n, i ); //对每个内部节点做下滤，合并子堆
0004 } //heapify

和每次下滤都和节点的高度相关，方便起见考虑完全二叉树，$S=\sum {k * 2^{h-k}}=O (n)$

O (n) 是离线算法。用堆建 Huffman 树需要连删两个最小值再把和塞回去，nlogn

如果真是随机的其实朴素算法期望确实 O (n)，但如果插入个单调性强的序列就大量触发最坏情况。

堆排序

0001 template <typename T> void Vector<T>::heapSort( Rank lo, Rank hi ) { //0 <= lo < hi <= size
0002    T* A = _elem + lo; Rank n = hi - lo; heapify( A, n ); //将待排序区间建成一个完全二叉堆，O(n)
0003    while ( 0 < --n ) //反复地摘除最大元并归入已排序的后缀，直至堆空
0004       { swap( A[0], A[n] ); percolateDown( A, n, 0 ); } //堆顶与末元素对换，再下滤
0005 } //heapSort

建堆，每次删掉最大值并添加到 sorted。O (nlogn)

竞赛树

胜者树：每个内部节点都是更大的儿子的副本。

建树：原始数据作为叶子节点两两比较，直到最后角逐出最大者位于顶部。

删除：删除顶部，需要一路回溯到自己的叶子节点（每次找和自己数值一样的儿子），设置为负无穷，然后只针对这条路径重赛，角逐出新的冠军。也就是只有优胜者的祖先需要重赛。

建树：O (n)；空间：O (n)；删除并重赛：O (logn)

空间的话堆不需要额外空间，胜者树需要 O (n)；时间建堆和建树都是 O (n)，但堆常数小，不过删除元素并下滤每次要比较 2 次，胜者树只需要 1 次

败者树：

内部节点记录的是败者，胜者继续上溯对决，增加根节点的父亲作为全局胜者。避免胜者树弯弯绕绕找邻居对决。

左式堆

右侧藤：右儿子组成的路径。合并时间正比于右侧藤总长

定义 npl (x)=x 到外部节点的最近距离 = 以 x 为根的最大满 “子” 树的高度

$npl(x)=1+min{npl(lc(x)),npl(rc(x))}$

左式堆限制：npl (lc)>=npl (rc)，于是 npl (x)=npl (rc)+1；左子堆的规模未必比右子堆大。

也就是说右侧藤长度被 logn 限制

合并：

0001 template <typename T> //合并以a和b为根节点的两个左式堆（递归版）
0002 BNP<T> merge( BNP<T> a, BNP<T> b ) {
0003    if ( !a ) return b; //退化情况
0004    if ( !b ) return a; //退化情况
0005    if ( *a < *b ) swap( a, b ); //确保a>=b
0006    ( a->rc = merge( a->rc, b ) )->parent = a; //将a的右子堆，与b合并
0007    if ( NPL(a->lc) < NPL(a->rc) ) //若有必要（宏隐藏了边界情况）
0008       swap( a->lc, a->rc ); //交换a的左、右子堆，以确保右子堆的npl不大
0009    a->npl = NPL(a->rc) + 1; //更新a的npl（宏隐藏了边界情况）
0010    return a; //返回合并后的堆顶
0011 } //本算法只实现结构上的合并，堆的规模须由上层调用者负责更新

先把大的调换到 a，把 a 的右子树和 b 合并作为 a 新的右子树，最后检查 npl 有无问题。

最多递归到 logn 就到底了，而每次操作都是 O (1)，所以合并操作是 O (logn)，准确来说 O (logn + logm)

插入：和单个节点构成的树合并，O (logn)

删除：堆顶的左右子堆合并