Class Code: AMC621 Instructor: Huilan Chang

<aside>

Definition. A (binary) heap推疊 (一種data structure) is an array that we can view as a nearly complete binary tree ( a binary tree 且每一層都是滿的除了最後一層可缺靠右的點)。

</aside>

Example.

特性: $A[1]$ is the root.

• There are two kinds of binary heap: max-heap and min-heap.
  • $A$ is a max-heap if $A[$PARENT$(i)]\geq A[i]$ for all node $i\neq$ root. e.g. $A=[9, 6, 8, 5, 3, 4]$ is a max-heap.
  • $A$ is a min-heap if $A[$PARENT$(i)]\leq A[i]$ for all node $i\neq$ root.

🔹 Maintaining the heap property

Assume that the binary trees rooted at LEFT($i$) and RITHT($i$) are max-heaps, but $A[i]$ may be smaller than its children.

MAX-HEAPIFY($A$, $i$) is to make the subtree rooted at node $i$ become a max-heap.

採遞迴的做法：Example. MAX-HEAPIFY($A$, $2$).　 注意：$A[2]$應放 $A[2]$, $A[LEFT(i)]$, $A[RIGHT(i)]$三者中的最大值。

Pseudocode.

註：此處的 $A$.heap-size 是 Python 語法，表示在定義的 Class 中 heap-size 這個屬性，可設定此屬性的值。 $A$.heap-size 可被指定 and $A$.length=len($A$) is fixed。

$l\leq A$.heap-size 代表 $i$有左小孩

Analysis of MAX-HEAPIFY:

• Definition. The height高度 of a node in a heap is the number of edges on the longest downward path from the node to a leaf. The height of a heap is the height of its root.
• The computational complexity of MAX-HEAPIFY($A$, $i$) is proportional(正比於) to the height of node $i$.
• If the subtree rooted at node $i$ has $n$ nodes, the height of node $i$ is at most $\lg(n)$. Proof. Let $h$ be the height of node $i$. Then ****$n=1+2+\cdots+2^{h-1}+r=2^h-1+r$, where $1\leq r\leq 2^{h}$. Then $2^h\leq n\leq 2^{h+1}-1$, hence $h\leq \lg(n)<h+1$. QED

<aside>

Lemma. If the subtree rooted at node $i$ has $n$ nodes, then MAX-HEAPIFY($A$, $i$) takes $O(\lg n)$ time.

</aside>

🔹 Build a heap and the heapsort algorithm

HEAPSORT($A$)

1 BUILD-MAX-HEAP($A$)

2 for $i=A$.length downto $2$