文章目录

玩了下tikz^_^

We can build a heap by repeatedly calling MAX-HEAP-INSERT to insert the elements into the heap. Consider the following variation of the BUILD-MAX-HEAP procedure.

BUILD-MAX-HEAP’(A)
A.heap-size = 1
for i = 2 to A.length
MAX-HEAP-INSERT(A, A[i])
Do the procedures BUILD-MAX-HEAP and BUILD-MAX-HEAP’ always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.
Show that in the worst case, BUILD-MAX-HEAP’ requires Θ(nlgn) time to build a n-element heap.

存在反例,

若输入如下数组

BUILD-MAX-HEAP得到结果是

而BUILD-MAX-HEAP’

如果,BUILD-MAX-HEAP每次都是递增插入的话,每次都取MAX-HEAP-INSERT(A,A[i])的最坏情况,故整个函数也达到最坏情况。
MAX-HEAP-INSERT(A,A[i])的最坏情况即为$lg(\lceil n \rceil) - 1个SWAP$

存在$T(n) = T(n-1) +\lfloor lg( n )\rfloor(n>=2)$, 假设$T(n) = \Theta(nlgn)$ , 即存在$T(n) <= cnlg(n) 对于某些 c$

对困难的边境情况不考虑,即

$$
T(n) <= \lfloor lg( n )\rfloor + c(n-1)lg(n-1) \\
<= lgn + cnlg(n-1)-clg(n-1) \\
=cnlg(n-1)+lg\frac{n}{(n-1)^c}\\
< cnlgn + 0(n>=3, c = 2)
$$

同时下界

$$
T(n) - T(n-1) = \lfloor lg( n )\rfloor(n>=2) \\
T(n) = \lfloor lg( n )\rfloor+\lfloor lg( n-1 )\rfloor+ \lfloor lg( n-2 )\rfloor…\\
> lgn! -n = Θ(nlgn) - Θ(n) = Θ(nlgn)(同样适合证明上界)
$$

故$T(n) = \Theta(nlgn)$

文章目录