Python實現堆排序

一、堆排序簡介

堆排序(Heap Sort)是利用堆這種數據結構所設計的一種排序算法。

堆的結構是一棵完全二叉樹的結構，并且滿足堆積的性質：每個節點(葉節點除外)的值都大于等于(或都小于等于)它的子節點。

關于二叉樹和完全二叉樹的介紹可以參考：http://www.zmynmublwnt.cn/article/217579.html

堆排序先按從上到下、從左到右的順序將待排序列表中的元素構造成一棵完全二叉樹，然后對完全二叉樹進行調整，使其滿足堆積的性質：每個節點(葉節點除外)的值都大于等于(或都小于等于)它的子節點。構建出堆后，將堆頂與堆尾進行交換，然后將堆尾從堆中取出來，取出來的數據就是最大(或最小)的數據。重復構建堆并將堆頂和堆尾進行交換，取出堆尾的數據，直到堆中的數據全部被取出，列表排序完成。

堆結構分為大頂堆和小頂堆：

1. 大頂堆：每個節點(葉節點除外)的值都大于等于其子節點的值，根節點的值是所有節點中最大的，所以叫大頂堆，在堆排序算法中用于升序排列。

2. 小頂堆：每個節點(葉節點除外)的值都小于等于其子節點的值，根節點的值是所有節點中最小的，所以叫小頂堆，在堆排序算法中用于降序排列。

二、堆排序原理

堆排序的原理如下：

1. 將待排序列表中的數據按從上到下、從左到右的順序構造成一棵完全二叉樹。

2. 將完全二叉樹中每個節點(葉節點除外)的值與其子節點(子節點有一個或兩個)中較大的值進行比較，如果節點的值小于子節點的值，則交換他們的位置(大頂堆，小頂堆反之)。

3. 將節點與子節點進行交換后，要繼續比較子節點與孫節點的值，直到不需要交換或子節點是葉節點時停止。比較完所有的非葉節點后，即可構建出堆結構。

4. 將數據構造成堆結構后，將堆頂與堆尾交換，然后將堆尾從堆中取出來，添加到已排序序列中，完成一輪堆排序，堆中的數據個數減1。

5. 重復步驟2,3,4，直到堆中的數據全部被取出，列表排序完成。

以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 進行升序排列為例。列表的初始狀態如下圖。

要進行升序排序，則構造堆結構時，使用大頂堆。

1.將待排序列表中的數據按從上到下、從左到右的順序構造成一棵完全二叉樹。

2. 從完全二叉樹的最后一個非葉節點開始，將它的值與其子節點中較大的值進行比較，如果值小于子節點則交換。24是最后一個非葉子節點，它只有一個子節點21，24大于21，不需要交換。

3. 繼續將倒數第二個非葉節點的值與其子節點中較大的值進行比較，如果值小于子節點則交換。節點30有兩個子節點5和36，較大的是36，30小于36，交換位置。

4. 重復對下一個節點進行比較。7小于45，交換位置。

5. 繼續重復，50大于27，不需要交換位置。如果不需要進行交換，則不用再比較子節點與孫節點。

6. 繼續重復，17小于45，交換位置。

7. 17和45交換位置之后，17交換到了子節點的位置，還需要繼續將其與孫節點進行比較。17大于15，不需要交換。

8. 繼續對下一個節點進行比較，10小于50，交換位置。

9. 10和50交換位置之后，10交換到了子節點的位置，還需要繼續將其與孫節點進行比較。10小于于27，交換位置。

10. 此時，一個大頂堆構造完成，滿足了堆積的性質：每個節點(葉節點除外)的值都大于等于它的子節點。

11. 大頂堆構建完成后，將堆頂與堆尾交換位置，然后將堆尾從堆中取出。將50和21交換位置，交換后21到了堆頂，50(最大的數據)到了堆尾，然后將50從堆中取出。

12. 將50從堆中取出后，找到了待排序列表中的最大值，50添加到已排序序列中，第一輪堆排序完成，堆中的元素個數減1。

13. 取出最大數據后，重復將完全二叉樹構建成大頂堆，交換堆頂和堆尾，取出堆尾。這樣每次都是取出當前堆中最大的數據，添加到已排序序列中，直到堆中的數據全部被取出。

14. 循環進行 n輪堆排序之后，列表排序完成。排序結果如下圖。

三、Python實現堆排序

# coding=utf-8
def heap_sort(array):
  first = len(array) // 2 - 1
  for start in range(first, -1, -1):
      # 從下到上，從右到左對每個非葉節點進行調整，循環構建成大頂堆
      big_heap(array, start, len(array) - 1)
  for end in range(len(array) - 1, 0, -1):
      # 交換堆頂和堆尾的數據
      array[0], array[end] = array[end], array[0]
      # 重新調整完全二叉樹，構造成大頂堆
      big_heap(array, 0, end - 1)
  return array


def big_heap(array, start, end):
  root = start
  # 左孩子的索引
  child = root * 2 + 1
  while child <= end:
      # 節點有右子節點，并且右子節點的值大于左子節點，則將child變為右子節點的索引
      if child + 1 <= end and array[child] < array[child + 1]:
          child += 1
      if array[root] < array[child]:
          # 交換節點與子節點中較大者的值
          array[root], array[child] = array[child], array[root]
          # 交換值后，如果存在孫節點，則將root設置為子節點，繼續與孫節點進行比較
          root = child
          child = root * 2 + 1
      else:
          break


if __name__ == '__main__':
  array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
  print(heap_sort(array))

運行結果：

[5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]

代碼中，先實現一個big_heap(array, start, end)函數，用于比較節點與其子節點中的較大者，如果值小于子節點的值則進行交換。代碼中不需要真正將數據都添加到完全二叉樹中，而是根據待排序列表中的數據索引來得到節點與子節點的位置關系。完全二叉樹中，節點的索引為i，則它的左子節點的索引為2*i+1，右子節點的索引為2*i+2，有n個節點的完全二叉樹中，非葉子節點有n//2個，列表的索引從0開始，所以索引為0~n//2-1的數據為非葉子節點。

實現堆排序函數heap_sort(array)時，先調用big_heap(array, start, end)函數循環對非葉子節點進行調整，構造大頂堆，然后將堆頂和堆尾交換，將堆尾從堆中取出，添加到已排序序列中，完成一輪堆排序。然后循環構建大頂堆，每次將最大的元素取出，直到堆中的數據全部被取出。

四、堆排序的時間復雜度和穩定性

1. 時間復雜度

在堆排序中，構建一次大頂堆可以取出一個元素，完成一輪堆排序，一共需要進行n輪堆排序。每次構建大頂堆時，需要進行的比較和交換次數平均為logn(第一輪構建堆時步驟多，后面重建堆時步驟會少很多)。時間復雜度為 T(n)=nlogn，再乘每次操作的步驟數(常數，不影響大O記法)，所以堆排序的時間復雜度為 O(nlogn) 。

2. 穩定性

在堆排序中，會交換節點與子節點，如果有相等的數據，可能會改變相等數據的相對次序。所以堆排序是一種不穩定的排序算法。

到此這篇關于Python實現堆排序案例詳解的文章就介紹到這了,更多相關Python實現堆排序內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！

原文鏈接：https://blog.csdn.net/weixin_43790276/article/details/104033696