-->
当前位置:首页 > 题库

单选题:The potential of a skew heap is defined to be the total number o

Luz5年前 (2021-05-10)题库761
The potential of a skew heap is defined to be the total number of right heavy nodes. The weight of a node, $$w(x)$$, is defined to be the number of descendants of $$x$$ (including $$x$$). A non-root node is said to be **heavy** if its weight is greater than half the weight of its parent.

***Lemma 1***: At most one child is heavy, of all children of any node.

***Lemma 2***: On any path from node $$x$$ down to a descendant $$y$$, there are at most $$\lfloor log_2 \frac{w(x)}{w(y)} \rfloor$$ light nodes, excluding $$x$$. In particular, any path in an $$n$$-node tree contains at most $$\lfloor log_2 n \rfloor $$ light nodes.

Define the following functions:
* *makeheap* : create a new, empty heap
* *findmin* : return the minimum key in the heap
* *insert* : insert a key in the heap
* *deletemin* : delete the minimum key from the heap
* *merge* : merge two heaps

Then for any $$n$$-node skew heaps, which of the following is **FALSE**? @[D](5)

A. The amortized time of a merge operation is $$O(logn)$$
B. The amortized time of a makeheap operation is $$O(1)$$
C. The amortized time of a findmin is $$O(1)$$
D. The amortized time of a deletemin operation is $$O(1)$$



A.The amortized time of a merge operation is $$O(logn)$$
B.The amortized time of a makeheap operation is $$O(1)$$
C.The amortized time of a findmin is $$O(1)$$
D.The amortized time of a deletemin operation is $$O(1)$$


答案:D