[資料結構] CH19. Heaps

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

• 我們在[資料結構] CH15. Heap and Shell Sorts & Comparisons有學過所謂的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