5 Binomial Queue

基本概念

To implement a binomial queue, __ is true.

\(\textnormal{A}\). The roots of binomial trees are stored in a linked list

\(\textnormal{B}\). Left-child-next-sibling structure is used to represent each binomial tree

\(\textnormal{C}\). The subtrees of a binomial tree are linked in increasing sizes

\(\textnormal{D}\). None of the above

答案

二项队列将所有子树的根节点存储在数组中（索引为二项树的阶数），使用 Left-child-next-sibling 结构维护二项树，并按降序维护子树，故正确答案为 \(\textit{B}\)

时间复杂度

Making \(N\) insertions into an initally empty binomial queue takes \(O(N)\) time in the worst case.

答案

\(\textnormal{T}\)

Which of the following statements about binomial queue is FALSE?

\(\textnormal{A}\). The amortized time of insertion is \(Θ(1)\). \(\qquad\) \(\textnormal{B}\). Find-Min operation can take \(Θ(1)\).

\(\textnormal{C}\). Delete-Min operation can take \(Θ(log N)\). \(\qquad\) \(\textnormal{D}\). The worst case of insertion is \(Θ(N)\).

答案

二项队列插入的最坏情况是合并 \(O(\log N)\) 棵二项树，最坏时间复杂度是 \(O(\log N)\)，答案为 \(\textnormal{D}\)

节点深度

In a binomial queue with \(100\) nodes, how many nodes have depth \(1\) (the root has depth \(0\))?

答案

\(B_k\) 中深度为 \(1\) 的节点数为 \(k\)，\(100 = 2^6 + 2^5 + 2^2\)，故答案为 \(13\)