4 Leftist Heaps and Skew Heaps¶
1 Leftist Heaps¶
基本性质
For a leftist heap, the NPL of each node is 1 greater than the NPL of its right child.
答案
\(\mathrm{Npl}(X) = \min\{\mathrm{Npl}(C) + 1 \text{ for all } C \text{ as children of } X\}\)，故答案为 \(\textnormal{T}\)
A perfectly balanced tree forms if keys 1 to \(2^k−1\) are inserted in order into an initally empty leftist heap.
答案
\(\textnormal{T}\)
A leftist heap with the null path length of the root being \(r\) must have at least \(2^{r+1}-1\) nodes.
答案
\(\textnormal{T}\)
A leftist heap with N nodes on the right path must have at least \(2^N-1\) nodes.
答案
\(\textnormal{T}\)
After merging two Leftist Heaps H1 and H2, the NPL of the resulted Leftist Heap will be no more than min(NPL of H1, NPL of H2)+1.
答案
\(\textnormal{F}\)
时间复杂度
For a leftist heap with \(N\) nodes, the worst-case running time of all operations (insert/delete min/merge) is \(\Theta(N)\).
答案
最坏时间复杂度为 \(O(\log N)\)，答案为 \(\textnormal{F}\)
The time complexity of merging two leftist heap can be as bad as \(\Omega(N)\), where \(N\) is the number of elements in the heap.
答案
\(\textnormal{F}\)
DecreaseKey can always be efficiently supported by leftist heaps in \(O(logN)\) where \(N\) is the total number of nodes.
答案
左偏堆的左路径长度可能为 \(O(N)\)，若目标节点在左链最底层，向上冒泡的路径长度为 \(O(N)\)，时间复杂度退化为 \(O(N)\)，答案为 \(\textnormal{F}\)
左偏堆的构建
We can perform BuildHeap for leftist heaps by considering each element as a one-node leftist heap, placing all these heaps on a queue, and performing the following step: Until only one heap is on the queue, dequeue two heaps, merge them, and enqueue the result. Which one of the following statements is FALSE?
\(\text{A}.\) in the k-th run, \(⌈N/2^k⌉\) leftist heaps are formed, each contains \(2^k\) nodes
\(\text{B}.\) the worst case is when \(N = 2^k\) for some integer \(K\)
\(\text{C}.\) the time complexity \(T(N) = O(\frac{N}{2} log2^0 + \frac{N}{2^2} log2^1 + \frac{N}{2^3} log2^2 + ⋯ + \frac{N}{2^k} log2^{k-1})\) for some integer \(K\) so that \(N = 2^k\)
\(\text{D}.\) the worst case time complexity of this algorithm is \(Θ(NlogN)\)
答案
根据分析，最差时间复杂度为 \(O(N)\)，答案为 \(\textnormal{D}\)
To build a leftist heap, we can start from placing all the keys as single-node heaps on a queue, and perform the following until only one heap is on the queue: dequeue two heaps, merge them, and enqueue the result.
Then the best description of the time complexity of this procedure is:
\(\textnormal{A}\). \(O(\sqrt{N})\) \(\qquad\) \(\textnormal{B}\). \(O(N)\) \(\qquad\) \(\textnormal{C}\). \(O(\log N)\) \(\qquad\) \(\textnormal{D}\). \(O(N \log N)\)
答案
左偏堆的合并操作时间复杂度为 \(O(\log s)\)（\(s\) 是合并后堆的大小），假设初始有 \(N\) 个单节点堆，则：
- 第 1 轮：合并 \(\dfrac{N}{2}\) 次，每次合并两个大小为 1 的堆，合并后堆大小为 2，时间 \(O(\log 2) = O(1)\)
- 第2轮：合并 \(\dfrac{N}{4}\) 次，每次合并两个大小为 2 的堆，合并后堆大小为 4，时间 \(O(\log 4) = O(2)\)
- 第 \(i\) 轮：合并 \(\dfrac{N}{2^i}\) 次，每次合并后堆大小为 \(2^i\)，时间 \(O(\log 2^i) = O(i)\)
- 直到第 \(k\) 轮（\(2^k = N\)），合并 1 次，时间 \(O(\log N)\)
总时间 \(= N \times \sum\limits_{i=1}^k \frac{i}{2^i} = 2N = O(N)\)，答案为 \(\textnormal{B}\)
2 Skew Heaps¶
基本性质
A perfectly balanced tree forms if keys \(1\) to \(2^k -1\) are inserted in order into an initally empty skew heap.
答案
\(\textnormal{T}\)
Skew heaps do not need to maintain the null path length of any node.
答案
\(\textnormal{T}\)
Comparing to leftist heaps, skew heaps are always more efficient in space.
答案
\(\textnormal{T}\)
The right path of a skew heap can be arbitrarily long.
答案
\(\textnormal{T}\)
时间复杂度
For a skew heap with \(N\) nodes, the worst-case running time of all operations (insert/delete min/merge) is \(O(N)\).
答案
在最坏情况下，斜堆所有操作（合并、插入、删除最小值等）的时间复杂度均为 \(O(N)\)，但摊还复杂度都是 \(O(\log N)\)，答案为 \(\textnormal{T}\)
A skew heap is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than balanced binary heaps. The worst case time complexities for Merge, Insert, and DeleteMin are all \(O(N)\), while the amortited time complexities for Merge, Insert, and DeleteMin are all \(O(\log N)\).
答案
\(\textnormal{T}\)
轻节点
轻节点和重节点
对于斜堆中的节点 \(x\)，设其左子树大小为 \(t\)、右子树大小为 \(s\)：
- 若 \(s < \frac{t}{2}\)，则 \(x\) 称为轻节点
- 若 \(s \geq \frac{t}{2}\)，则 \(x\) 称为重节点
The number of light nodes along the right path of a skew heap is \(O(\log N)\).
答案
沿着右路径，每遇到一个轻节点，子树大小至少减半。由于根节点的子树大小为 \(N\)，因此轻节点的数量最多为 \(O(\log N)\)，答案为 \(\textnormal{T}\)
The number of light nodes along the right path of a skew heap is \(\Omega (\log N)\).
答案
\(\textnormal{F}\)
3 Leftist Heaps V.S. Skew Heaps¶
堆的构建
When a leftist heap can be implemented recursively, its counterpart skew heap may not be.
答案
在最坏情况下，由于右侧路径可以任意长，因此递归实现可能因为栈空间不足而无法实现，答案为 \(\textnormal{T}\)
类比
The relationship of skew heaps to leftist heaps is analogous to the relation between splay trees and AVL trees.
答案
\(\textnormal{T}\)
The relation of splay trees to AVL trees is analogous to the relation between binomial queues and priority queues.
答案
\(\textnormal{F}\)