Aloha～又是我少女人妻 Uerica！今天是教師節啊～大家小時候都會寫感謝恩師的卡片嗎？記得剛上國小的時候還有體罰，教師節時爸媽送了老師一面金牌寫 "感謝恩師" ，然後拜託老師如果我不乖就用力打，嗚嗚嗚到底為什麼啦～當時的我嚇到乖得不得了呢 QQ...。

堆積 (heap)

堆積是圖形結構中的樹狀結構中的一種，用於實踐優先佇列 (Priority Queue) 。利用保持資料結構的一定規則 (從小到大或從大到小) ，來確保拿取資料的效率。

堆積的定義與特性

堆積一種特殊的二元樹資料結構，但不全然相同，每個節點(node)最多只有兩個子節點，而子節點與父節點之間要維持一定規則，同層的兄弟節點則無規則限制，但同一層要維持從左到右新增節點，滿了才可增加下一層。

堆積的種類

• 最小堆積 Min heap : 父節點永遠小於子節點
• 最大堆積 Max heap : 父節點永遠大於子節點

常見的基本操作

插入 Insert

假設要插入一個資料元素到遵循最小堆積的結構中。

插入資料元素時，都先從最左下方開始。

插入元素後比對是否符合父節點永遠小於子節點這個規則。

若不符合規則，則交換位置，直到符合為止。

刪除 Delete

從最小的根節點刪除或取出。

順序最後一個子節點做替補。

若不符合父節點永遠小於子節點這個規則則做交換，選擇最小的子節點做交換。

再做比對，再交換。

直到符合規則為止。

堆積的時間複雜度

• 因根節點永遠是最小或最大值，故取最小或最大值的時間複雜度為 O(1)
• 若取出元素需重整資料結構，時間複雜度為 O(log n)

參考資料

資料結構大便當： Binary Heap

堆積：維基百科

【資料結構和演算法】堆積, 堆積排序和優先佇列

Heap Tree

好啦～今天就先介紹到這裡了，大家掰掰明天見啦！話說後來的老師都沒收金牌，我就以為可以皮了，然後...然後就被打爆了 XD。