[Algo] 6.1 Heaps

heap 的定義
The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree. 這個 heap 不是指 memory layout 中的 heap，在這裡它是個特別的 data structure，但它僅僅是個 array 而已，雖然形狀看起來像棵 binary tree。我們在探討 heap 的特性時是把它想像成一顆 binary tree，但是他儲存的方式是個 array。但是 heap 當然可以是個 d-ary tree，不一定非得要是 binary tree。

heap 的 attribute
令 A 為一個 array 可以用來代表一個 heap，我們可以把 array A 視為一個 object，一個有heap特性的 object，接下來我們來看這個 object 有哪些 attribute：
(1) length[A]：array A 裡面中的 element 的個數
(2) heap-size[A]：array A 中被儲存為 heap 裡面的 element 個數
當然，我們可以從這兩個 attributes 得到一些特性：  
(i)heap-size[A] $\leq$ length[A]
以及
(ii)A[1 ... heap-size[A]]裡面的 element 才是 heap 裡面的 element。

heap 的圖解

heap procedures

tree 的 root 為 A[1]，給定一個 index i，我們可以得到它的 parent, left child, right child：
@{
\proc{Parent}(i)
\li \Return $\lfloor i/2 \rfloor$
}@
@{
\proc{Left}(i)
\li \Return $2i$
}@
@{
\proc{Right}(i)
\li \Return $2i + 1$
}@

heap property
有兩種不同的 binary heap：
(1) max-heap
    (i) max-heap property：for every node other than the root, A[PARENT(i)] $\geq$ A[i]，注意的是左右 sibling 是沒有誰必須大於誰的規定
    (ii) root 是整個 heap 裡面最大的 element
    (iii) 任何一個 node 底下的 subtree 裡，都是這個 node 的值最大
(2) min-heap
    min-heap 基本上跟 max-heap 的性質類似，只不過大小顛倒相反而已。

heap height 的定義
(1) We define the height of a node in a heap to be the number of edges on the longest simple downward path from the node to a leaf.
(2) We define the height of the heap to be the height of its root.
所以 heap 的 height 都是由 leaf 往上數上來的，leaf 的 height 都是 0，上圖的 heap 的 height 是 3，值是 8 的那個 node 的 height 是 1。

一個有 n 個 element 的 binary heap，他的 height 是$\Theta(\lg n)$，所有 basic operations 的 running time 都是跟這個 heap 的 height 有關係，所以都是 $O(\lg n)$。