前言

花了兩文的篇幅去介紹了 BST，現在要進入新的資料結構 Heap，此章節會先談及此資料結構的定義、接著在談針對 Heap 的各種操作，在進入定義之前，我們要先來複習 Complete Binary Tree，幫助大家比較好理解接下來的 Heap

Complete BT 複習

在此系列 (04) 篇文章，有介紹過 BT，裡面二元樹的種類有一項是 Complete，在該篇文章，定義了 Complete BT 令高度 =k, 節點數 =n
須滿足以下兩點

1. 節點數限制
2. 節點由上至下、左至右增長

除此之外，也提過 Complete BT 最適合的儲存結構是 Array，因為可以直接存入而不浪費空間，也可以輕易存取父點與左右子點，由於這個特點，等等在使用 Heap 進行操作的時候會更加地方便

Heap def

Definition

Heap 有分成 Max, Min Heap，這邊以 Max Heap 為例子
為一棵 Complete BTree，若此樹不為空則滿足以下幾點

1. 子點必小於等於父點
2. Root 必為最大值

Heap 各種操作

在進行這些操作的時候，以 Max Heap 為例子

Insert x

1. 將 x 放置最尾端（目前 last node 的下一個），成為 last node
2. 挑戰父點直到無法挑戰或失敗
   插入 55 此點入 Heap
   

Delete Max

1. 先將 root 移除
2. 將 last node 放到 root 的位置 (x)
3. x 從 root 往下調整為 heap 型態
   

下一章節再繼續介紹怎麼利用 Bottom-up 建立 Heap，還有其他操作