[資料結構] Heap 的概念與實作

Heap是一種資料結構，使用一維陣列來儲存
在理解上可以把他想成是一顆tree

而heap有兩個property:

1. Heap property: 
1. min-heap: root必為最小的值
2. max-heap: root必為最大的值
2. Shape property: 由左至右，每層都填滿

因為擁有這樣的特性，heap可以快速的拿到最大或最小值，因此也可以拿來做sorting -- Heapsort，時間複雜度是 O(nlogn)

概念：

圖片來源：https://en.wikipedia.org/wiki/Heap_(data_structure)

上圖是max-heap的範例，也就是說root永遠是最大值。如：100 > 19 和 36，19 > 17 和 3 等。而在實作時是用陣列的方式儲存，依序是：100, 19, 36, 17, 3, 25, 1, 2, 7。

以下將分成 insert及delete說明。

Insert:

由於heap一定是由左到右依序填滿，因此我們可以將要insert進來的node先放在整個tree的最後面，再慢慢地與root交換，直到符合heap的要求。

以上圖為例，假設我們現在要insert一個新的node，值是30，則我們先將其放在3的下面，當成3的子節點，再往上看他的root。發現30 > 3，則交換。再往上看，發現30 > 19，則再交換，接著再往上看，發現 30 < 100，於是停止。

Delete

刪除的時候也是一樣，當我們拿掉root的時候，先將整個陣列的最後一個值放上來，再做調整。以上圖為例，假如我們要刪掉36這個node，則將7移到36的位置，再往下看他的子節點，發現25 > 7 則跟25交換，接著再看右節點，發現 25 > 1，所以停止。