[Algo] Exercise 6.1

Exercise 6.1-1
What are the minimum and maximum numbers of elements in a heap of height h?
(1) minimum
$1 + 2 + 2^2 + \cdots + 2^{h-1} + 1 = \frac{2^h - 1}{2-1} + 1 = 2^h$
(2) maximum
$1 + 2 + 2^2 + \cdots + 2^h = \frac{2^{h+1} - 1}{2-1} = 2^{h+1} - 1$


Exercise 6.1-2
Show that an n-element heap has height $\lfloor \lg n \rfloor$.
Let h be the height of an n-element heap. From exercise 6.1-1, we know $2^h \leq n < 2^{h+1}$. We can obtain $h \leq \lg n < h+1$, thus $h = \lfloor \lg n \rfloor$


Exercise 6.1-3
Show that in any subtree of a max-heap, the root of the subtree contains the largest value occuring anywhere in that subtree.
如果最大的 element 不是出現在 subtree 的 root 的話，那就會違背 max-heap property。


Exercise 6.1-4
Where in a max-heap might the smallest element reside, assuming that all elements are distinct?
因為 max-heap property，最小的 node 一定會出現在 leaf 裡面，但不保證是最後一個 leaf。


Exercise 6.1-5
Is an array that is in sorted order a min-heap?
yes, 但是 min-heap 不一定是 in sorted order。


Exercise 6.1-6
Is the sequence <23, 17, 14, 6, 13, 10, 1, 5, 7, 12> a max-heap?
No, 畫圖出來就知道了。6 的 right child 是 7。


Exercise 6.1-7
Show that, with the array representation for storing an n-element heap, the leaves are the nodes indexed by $\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \ldots, n$.
最後一個 node 必為leaf，而且他的 parent(index: $\lfloor n/2 \rfloor$)必為 array 中最後一個非 leaf 的 node，所以從這個 node 之後的所有 node就是 leaf 了。