# [資料結構] CH19. Heaps

- *注意：該筆記並非上課期間的隨堂筆記，可能有些東西我會筆誤，請見諒。*

* 我們在[[資料結構] CH15. Heap and Shell Sorts & Comparisons](/JMUqDnpaRSa2ACIXgcFT5Q)有學過所謂的`Heap Sort`了，我們複習一下`Heap Tree`的特性：
* 每個節點一定比自己的小孩還要大/小。
* 進行**插入**，先把新節點放在樹葉，照情況向上交換。
* 進行**刪除**，將節點與最後加入的樹葉交換，移除該樹葉，依情況交換。
* 接著我們要介紹一些更進階的`Heap Tree`。

## Binomial Tree

* `Binomial Tree`是一種全新的樹狀結構，它擁有以下特性：
* 
* 一棵Binomial Tree $B_i$ 裡面擁有 $2^i$ 個節點。
* 一棵Binomial Tree $B_i$ 它的高度為 $i$ 。
* 一棵Binomial Tree $B_i$ 它樹根裡面的每個節點都可以當成一個新的子樹的樹根，且它們分別為 $B_{i-1}$、$B_{i-2}$...$B_0$ 。

### Binomial Heap

* 現在我們讓Binomial Tree加入Heap Tree的特性，想想看它會變成什麼樣子。
* 它應該和上圖的形狀很像，但節點間的大小必須上大於下(下大於上)：
* 
* 每一個Binomial Tree都成為了一棵Heap Tree，也就是說一棵Binomial Heap其實就是一個Heap的集合。

#### 如何找到最小值/最大值

* 在一棵Heap裡面，我們最想知道的就是他的最小值/最大值(取決於是Min Heap還是Max Heap)，因此我們現在轉換成Binomial Heap也想知道這件事情。
* 請注意，在Binomial Heap中每個Heap Tree可以說是獨立的，也就是說它們的樹根值並不一定存在特定的大小關係。
* 然而它每個Heap依然維持最小/最大的特性，因此我們只需要去遍歷每個樹根，去紀錄極值即可。
* 

## Fibonacci Heaps

* Fibonacci Heaps是一個樹的集合。
* 它像是不嚴謹的Binomial Tree，雖然每一棵樹都符合Heap Tree，但沒有其他的特性。
* 
* 這樣的樹在你的資料需要進行大量分類時很好用，因為對於找尋最小/最大值，你一樣只需要遍歷每個樹根。
* 一個完整的Fibonacci Heaps結構，每個節點的兄弟之間也需要有連結：
* 

###### tags: `DS` `note`