【数据结构笔记】优先级队列PriorityQueue

堆序性质：除了根节点，其他节点都不大（小）于父节点

进而根节点是最大（小）堆的最大（小）元

完全二叉堆

物理上是Vector

逻辑上是完全二叉树

层次遍历序列与物理存储顺序相同
Rank为k的左孩子Rank为1+2k
Rank为k的右孩子Rank为2+2k
Rank为k的父节点Rank为⌊(k-1)/2⌋

上滤插入

在Vector末尾插入元素e
计算e的父节点的Rank，找到父节点，检查二者大小
- 如果父节点更优，完成
- 如果父节点更优，就交换二者数据项
  - e的数据项在逻辑上的完全二叉树中上升一层
- 仅需比较1次
如此循环上滤，直到完成或升为根节点

最坏情况时间复杂度O(logn)
平均情况时间复杂度O(1)
- 最后两层占总节点数不少于一半，平均最多上升一层

下滤删除

把Vector末尾元素r与堆顶元素互换
计算r的所有孩子节点的Rank，找到所有孩子节点，检查大小
- 如果无孩子节点更优，完成
- 如果有孩子节点更优，r与更大的孩子节点交换
  - r的数据项在逻辑上的完全二叉树中下降一层
- 需比较2次
如此循环下滤，直到完成或降为叶节点

期望运行时间为O(logN)

最后两层占总节点数不少于一半

Floyd建堆

对于规模为n的输入，组织为Vector

n/2以前的节点有孩子节点
按Rank从高到低依次下滤
- 每次下滤结束，以当前节点为根的完全二叉堆维持堆序性
- 单次下滤复杂度为所在子堆的高度=本身高度

时间复杂度为O(n)

所有节点高度之和为O(n)

与n次调用BinHeap::insert()建堆比较

Floyd建堆渐进复杂度优
n较小时Floyd建堆无优势
Floyd建堆为离线算法， n次调用BinHeap::insert()建堆为在线算法

【2016-THU-Fin】完全二叉堆删除元素在最坏情况下时间复杂度为O(logn)，但平均情况下仅为O(1)。（×）

【2013，2016-THU-Fin】在使用Heapify批量建堆的过程中，改变同层节点的下滤次序对算法的正确性和时间效率都无影响。（√）

【2016-THU-Fin】二叉堆中某个节点秩为𝑘, 则其兄弟节点（假设存在）的秩为（AB）

A. 𝑘 + 1
B. 𝑘 − 1
C. 𝑘 + (−1)^𝑘
D. 𝑘 − (−1)^𝑘
E. 以上皆非

【2017-THU-Fin】当输入是理想随机的时候堆的delMax的平均复杂度是O(1)，尽管最坏是 O(logn)。（×）

min-max堆

（《数据结构与算法分析 Java语言描述》练习6.18）

d-堆

物理上是Vector

逻辑上是完全d叉树

层次遍历序列与物理存储顺序相同
Rank为k的第i个孩子Rank为i+kd
Rank为k的父节点Rank为⌊(k-1)/d⌋

上滤插入

单次上滤时间复杂度不变，堆高减小

时间复杂度降为O(\log_dn)

下滤删除

单次下滤需要d次比较，堆高减小

d=3时总时间复杂度减小
d=4时总时间复杂度不变
d>4时总时间复杂度增大

【2013-THU-Fin】多叉堆比二叉堆插入慢，删除快。（×）

【2014-THU-Fin】对于二叉堆，尽管多叉堆的高度更低，但无论是下滤一层还是整个下滤过程，时间成本反而都会增加。（×）

【2016-THU-Fin】与二叉堆相比，多叉堆 delMax()操作时间复杂度更高。（×）

左式堆

添加外部节点成为真二叉树

对任意内部节点node，有npl(node.leftChild) >= npl(node.rightChild)

零路径长Null Path Length（npl）：节点到孩子外部节点的最短路径长度
- npl(NULL) = 0
- npl(node) = 1 + min{npl(node.leftChild), npl(node.rightChild)}
  - 对于左式堆，npl(node) = 1 + npl(node.rightChild)
- npl(node) = node到孩子外部节点的最短路径长度 = 以node为根的最大满二叉树高度
左式堆的任意子树（堆）也是左式堆
左式堆的右侧链rChain是根节点通向外部节点的最短路径
- 右侧链：一直node = node.rightChild直到node = NULL
- npl(root) = rChain(r).length
- 如果npl(root) = d
  - 这表明其他通向外部节点的路径都不小于d
  - 左式堆截取深度d及以上部分为满二叉树

合并

递归地

把更优根的右子堆与另一根堆合并
过程中保持每次递归merge结束后，merge得到的根节点处都满足左式堆性质
- 左右子堆交换
- 因此最终合并得到的rChain可能来自于
更新全堆npl

时间复杂度为两堆rChain长度之和，为O(logmn)

（《数据结构与算法分析 Java语言描述》练习6.21）

插入

堆与单个节点合并

时间复杂度为O(logn)

删除

摘除根节点后得到的两个左式堆合并

时间复杂度为O(logn)

【2014-THU-Fin】对于任何一棵二叉树T，其右、左子树的规模之比称为右偏率。对于（常规）高度同为h的AVL树（A），红黑树（R），左式堆（L），若分别考查其右偏率所能达到的最大值，则在h足够大之后，三者按此指标的排列次序应是（）
A. L<R<A
B. L<A<R
C. R<A<L
D. A<R<L
E. 以上皆非