堆積排序(Heap Sort)演算法是利用完全二元樹(Complete Binary Tree),也就是堆積(Heap)結構來完成排序的演算法。雖然說要用到堆積結構,看起來好像很複雜似的,但其實這個只要一般的陣列結構(可以直接用要排序的陣列來製作)就能實作出來,而且實作出來的速度保證不會太慢,再怎麼差都會有O(nlogn)的時間複雜度。



堆積排序法(Heap Sort)

堆積排序法的概念

堆積排序有法兩個大步驟,第一個是把要排序的陣列製作成「最小堆積」(Min Heap)或是「最大堆積」(Max Heap)。如果要將陣列遞增排序的話就使用最大堆積;如果要遞減排序的話就使用最小堆積。接下來的步驟就是利用最大堆積和最小堆積來進行排序,方法和建立最大堆積或是最小堆積時是幾乎一樣的。

什麼是完全二元樹?完全二元樹是一種二元樹,它只允許最後一層(最底下那層)的節點數量可以不必填滿(若頂層是第1層,則第n層的最大節點數量為2n-1)。例如以下結構即為完全二元樹:

     5
   /   \
  1     3
 / \   /
6   2 4

什麼是最小堆積?最小堆積就是上層節點數值必定會小於下層節點數值的完全二元樹。例如以下結構即為最小堆積:

     1
   /   \
  2     5
 / \   /
4   6 3

什麼是最大堆積?最大堆積就是上層節點數值必定會大於下層節點數值的完全二元樹。例如以下結構即為最大堆積:

     6
   /   \
  5     3
 / \   /
4   2 1

陣列可以依照索引順序,由左至右、由上到下表示出一個完全二元樹。例如以上的最大堆積,可以是以下這個陣列:

索引    0   1   2   3   4   5
數值    6   5   3   4   2   1

堆積排序法的過程

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢?

我們先將這個陣列用完全二元樹的結構來表示,如下:

              69
            /    \
          /        \
        /            \
      81              30
     /  \            /  \
   /      \        /      \ 
  38       9      2       47
 /  \     /
61  32   79

由於我們要進行遞增,因此要先將這個完全二元樹變成最大堆積。於是我們從最下面的兩層開始,把比上層大的元素交換到上層。

首先看到47,由於它沒有子節點,因此還不用交換。

              69
            /    \
          /        \
        /            \
      81              30
     /  \            /  \
   /      \        /      \ 
  38       9      2       47*
 /  \     /
61  32   79

2,也沒有子節點,因此不用交換。

              69
            /    \
          /        \
        /            \
      81              30
     /  \            /  \
   /      \        /      \ 
  38       9      2*      47
 /  \     /
61  32   79

再來看到99有一個值為79的子節點。由於799大,所以要交換上來。

              69
            /    \
          /        \
        /            \
      81              30
     /  \            /  \
   /      \        /      \ 
  38       9*     2       47
 /  \     /
61  32   79↑

              69
            /    \
          /        \
        /            \
      81              30
     /  \            /  \
   /      \        /      \ 
  38      79+     2       47
 /  \     /
61  32   9*

此時9已沒有子節點了,結束交換。

再來看到3838有兩個子節點,對大的為61的子節點。由於6138大,所以要交換上來。

              69
            /    \
          /        \
        /            \
      81              30
     /  \            /  \
   /      \        /      \ 
  38*     79      2       47
 /  \     /
61↑32   9

              69
            /    \
          /        \
        /            \
      81              30
     /  \            /  \
   /      \        /      \ 
  61+     79      2       47
 /  \     /
38* 32   9

此時38已沒有子節點了,結束交換。

依此類推,剩下的最大堆積的建構過程如下:

              69
            /    \
          /        \
        /            \
      81              30*
     /  \            /  \
   /      \        /      \ 
  61      79      2       47↑
 /  \     /
38  32   9

              69
            /    \
          /        \
        /            \
      81              47+
     /  \            /  \
   /      \        /      \ 
  61      79      2       30*
 /  \     /
38  32   9

              69
            /    \
          /        \
        /            \
      81*             47
     /  \            /  \
   /      \        /      \ 
  61      79      2       30
 /  \     /
38  32   9

              69*
            /    \
          /        \
        /            \
      81↑            47
     /  \            /  \
   /      \        /      \ 
  61      79      2       30
 /  \     /
38  32   9

              81+
            /    \
          /        \
        /            \
      69*             47
     /  \            /  \
   /      \        /      \ 
  61      79↑    2       30
 /  \     /
38  32   9

              81+
            /    \
          /        \
        /            \
      79              47
     /  \            /  \
   /      \        /      \ 
  61      69*     2       30
 /  \     /
38  32   9

              81
            /    \
          /        \
        /            \
      79              47
     /  \            /  \
   /      \        /      \ 
  61      69      2       30
 /  \     /
38  32   9

至此,最大堆積就建立好了!

接下來的工作就是排序啦!由於我們現在已經知道這個結構中的最大值是最頂層的節點,且我們要把陣列做遞增排列。所以我們可以直接把頂層的節點,也就是最大值與陣列的最後一個元素做交換,如此一來我們的遞增排序就已經排好一個元素了。

              9*
            /    \
          /        \
        /            \
      79↑            47
     /  \            /  \
   /      \        /      \ 
  61      69      2       30
 /  \     /
38  32  81-

但別忘了要繼續維持住我們的最大堆積條件,所以還是得做交換才行。由於此時81已經在陣列的正確位置上,我們可以直接把它從最大堆積的考慮範圍中排除,不要再去動它了。

              79+
            /    \
          /        \
        /            \
       9*             47
     /  \            /  \
   /      \        /      \ 
  61      69↑    2       30
 /  \     /
38  32  81-

              79+
            /    \
          /        \
        /            \
      69              47
     /  \            /  \
   /      \        /      \ 
  61       9*     2       30
 /  \     /
38  32  81-

              79
            /    \
          /        \
        /            \
      69              47
     /  \            /  \
   /      \        /      \ 
  61       9      2       30
 /  \     /
38  32  81-

接下來就是讓32要與這個最大堆積結構中的最大值,也就是最頂層的節點做交換啦!之後的步驟都跟剛才把81換下來時一樣,如下:

              32*
            /    \
          /        \
        /            \
      69↑            47
     /  \            /  \
   /      \        /      \ 
  61       9      2       30
 /  \     /
38  79- 81-

              69+
            /    \
          /        \
        /            \
      32*             47
     /  \            /  \
   /      \        /      \ 
  61↑     9      2       30
 /  \     /
38  79- 81-

              69+
            /    \
          /        \
        /            \
      61              47
     /  \            /  \
   /      \        /      \ 
  32*      9      2       30
 /  \     /
38↑79- 81-

              69+
            /    \
          /        \
        /            \
      61              47
     /  \            /  \
   /      \        /      \ 
  38       9      2       30
 /  \     /
32* 79- 81-

              69
            /    \
          /        \
        /            \
      61              47
     /  \            /  \
   /      \        /      \ 
  38       9      2       30
 /  \     /
32  79- 81-

              32*
            /    \
          /        \
        /            \
      61↑            47
     /  \            /  \
   /      \        /      \ 
  38       9      2       30
 /  \     /
69- 79- 81-

              61+
            /    \
          /        \
        /            \
      32*             47
     /  \            /  \
   /      \        /      \ 
  38↑     9      2       30
 /  \     /
69- 79- 81-

              61+
            /    \
          /        \
        /            \
      38              47
     /  \            /  \
   /      \        /      \ 
  32*      9      2       30
 /  \     /
69- 79- 81-

              61
            /    \
          /        \
        /            \
      38              47
     /  \            /  \
   /      \        /      \ 
  32       9      2       30
 /  \     /
69- 79- 81-

              30*
            /    \
          /        \
        /            \
      38              47↑
     /  \            /  \
   /      \        /      \ 
  32       9      2       61-
 /  \     /
69- 79- 81-

              47+
            /    \
          /        \
        /            \
      38              30*
     /  \            /  \
   /      \        /      \ 
  32       9      2       61-
 /  \     /
69- 79- 81-

              47
            /    \
          /        \
        /            \
      38              30
     /  \            /  \
   /      \        /      \ 
  32       9      2       61-
 /  \     /
69- 79- 81-

              2*
            /    \
          /        \
        /            \
      38↑            30
     /  \            /  \
   /      \        /      \ 
  32       9      47-     61-
 /  \     /
69- 79- 81-

              38+
            /    \
          /        \
        /            \
       2*             30
     /  \            /  \
   /      \        /      \ 
  32↑     9      47-     61-
 /  \     /
69- 79- 81-

              38+
            /    \
          /        \
        /            \
      32              30
     /  \            /  \
   /      \        /      \ 
  2*       9      47-     61-
 /  \     /
69- 79- 81-

              38
            /    \
          /        \
        /            \
      32              30
     /  \            /  \
   /      \        /      \ 
  2        9     47-      61-
 /  \     /
69- 79- 81-

              9*
            /    \
          /        \
        /            \
      32↑            30
     /  \            /  \
   /      \        /      \ 
  2       38-    47-      61-
 /  \     /
69- 79- 81-

              32+
            /    \
          /        \
        /            \
       9*             30
     /  \            /  \
   /      \        /      \ 
  2       38-    47-      61-
 /  \     /
69- 79- 81-

              32
            /    \
          /        \
        /            \
       9              30
     /  \            /  \
   /      \        /      \ 
  2       38-    47-      61-
 /  \     /
69- 79- 81-

              2*
            /    \
          /        \
        /            \
       9              30↑
     /  \            /  \
   /      \        /      \ 
  32-     38-    47-      61-
 /  \     /
69- 79- 81-

              30+
            /    \
          /        \
        /            \
       9              2*
     /  \            /  \
   /      \        /      \ 
  32-     38-    47-      61-
 /  \     /
69- 79- 81-

              30
            /    \
          /        \
        /            \
       9              2
     /  \            /  \
   /      \        /      \ 
  32-     38-    47-      61-
 /  \     /
69- 79- 81-

              2*
            /    \
          /        \
        /            \
       9↑            30-
     /  \            /  \
   /      \        /      \ 
  32-     38-    47-      61-
 /  \     /
69- 79- 81-

              9+
            /    \
          /        \
        /            \
       2*             30-
     /  \            /  \
   /      \        /      \ 
  32-     38-    47-      61-
 /  \     /
69- 79- 81-

              9
            /    \
          /        \
        /            \
       2              30-
     /  \            /  \
   /      \        /      \ 
  32-     38-    47-      61-
 /  \     /
69- 79- 81-

              2
            /    \
          /        \
        /            \
       9-             30-
     /  \            /  \
   /      \        /      \ 
  32-     38-    47-      61-
 /  \     /
69- 79- 81-

這樣就完成排序啦!

heap-sort

堆積排序法的程式實作

堆積排序法的複雜度

以#{{n}}#來表示要排序的資料筆數。

項目備註
最差時間複雜度#{{O(n \log n)}}#
最佳時間複雜度#{{O(n)}}#要排序的元素值都一樣時。
平均時間複雜度#{{O(n \log n)}}#
額外最差空間複雜度#{{O(1)}}#
是否穩定