1.4.2 Heap Tree

定義:

最小堆積(Min heap):父節點若小於子節點, 則稱之.

最大堆積(Max heap):父節點若大於子節點, 則稱之.

(然而, 同一層的子節點則無須理會其大小關係)

一個堆積樹必定為完整二元樹(complete binary tree), 且通常會用陣列來實作.

所以大概長得像這樣(Min heap):

                            10 -> s
                            / \
                           /   \              s(parent), 2s(left), 2s+1(right)為節點在陣列中的索引關係
                          /     \                  
                         /       \ 
                        /         \
                       25 ->2s     15 ->2s+1
                     /   \        / \
                    30    26     20 29
                   /  \   / \    /
                  35  40 27 28  22

再來要知道怎麼建立堆積樹, 此處以上圖的min heap為例:

假設此處以一維陣列來儲存這棵樹, 現在要加入一個元素(12)

1. 首先, 新加入的元素會被放到最後的葉節點

                        10
                        / \
                       /   \
                      /     \
                     /       \ 
                    /         \
                   25          15
                 /   \        / \
                30    26     20 29
               /  \   / \    / \
              35  40 27 28  22  12 <---這裡

2. 然後新加入的節點會跟父節點做比對, 若小於父節點則往上升, 直至滿足堆積樹的條件為止才停下來

                        10
                        / \
                       /   \
                      /     \
                     /       \ 
                    /         \
                   25          15
                 /   \        / \
                30    26     12 29
               /  \   / \    / \
              35  40 27 28  22  20
   
                        10
                        / \
                       /   \
                      /     \
                     /       \ 
                    /         \
                   25          12 <---上不去惹
                 /   \        / \
                30    26     15 29
               /  \   / \    / \
              35  40 27 28  22 20

建立好堆積樹之後, 樹根一定是所有元素的最小值, 排序應用時:

1. 將最小值取出

2. 調整樹為最小堆積樹

不斷重複以上步驟就可達到排序的效果了, 其中, 取出最小值的做法是將樹根與最後一個葉節點做交換,然後切下葉節點, 並重新調整為堆積樹, 在這段過程中, 找出父節點跟兩個子節點中較小的一個做交換:

1. 將最小值取出(跟最後一個葉節點交換)

                     20 <---換到最上面
                     / \
                    /   \
                   /     \
                  /       \ 
                 /         \
                25          12
              /   \        / \
             30    26     15 29
            /  \   / \    / \
           35  40 27 28  22 10 <---被換下來了

2.將最小值取出(拿出來)

                     20
                     / \
                    /   \
                   /     \
                  /       \ 
                 /         \
                25          12
              /   \        / \
             30    26     15 29
            /  \   / \    /
           35  40 27 28  22 

           -> 10

3. 開始調整直到變成堆積樹

                     12
                     / \
                    /   \
                   /     \
                  /       \ 
                 /         \
                25         15
              /   \        / \
             30    26     20 29
            /  \   / \    / \_________>它往下換兩次後就停住了
           35  40 27 28  22 

           -> 10

因為此處假設使用一維陣列來儲存堆積樹, 所以一直重複此步驟的話, 每次將葉節點跟最小值交換的動作就是把最小值放到陣列的後端, 所以到最後陣列就變成排序好的狀態了.

整理:

堆積樹建立的過程(insert): 氣泡排序(樹葉到樹根), O(logn)

調整過程: 氣泡排序(樹根到樹葉), O(logn)

取出最大/小值: 直接拿根節點, Θ(1)

堆積排序法(Heap Sort)又被稱為改良的選擇排序法

・Best Case: O(nlogn)

・Worst Case: O(nlogn)

・Average Case: O(nlogn)

說明：

建立MaxHeap： Ο(n)

執行n-1次Delete Max：(n-1) × Ο(log n) = Ο( n log n)

・合併兩個Heap Tree: 最優方法是把兩個heap tree首尾相連放在一個陣列中, 然後構造新的heap tree. 時間複雜度為O(logn*logk), 其中n、k為兩個heap tree的元素數目.

• 範例程式: 點我