原創文章出自公眾號：「碼農富哥」，歡迎轉載和關注，如轉載請注明出處！
堆基本概念
堆排序是一個很重要的排序演算法，它是高效率的排序演算法，復雜度是O(nlogn)，堆排序不僅是面試進場考的重點，而且在很多實踐中的演算法會用到它，比如經典的TopK演算法、小頂堆用于實作優先級佇列，
堆排序是利用堆這種資料結構所設計的一種排序演算法，堆實際上是一個完全二叉樹結構，
問：那么什么是完全二叉樹呢？
答：假設一個二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹，
我們知道堆是一個完全二叉樹了，那么堆又分兩種堆：大頂堆 和 小頂堆
它們符合一個重要的性質：
- 小頂堆滿足： Key[i] <= key[2i+1] && Key[i] <= key[2i+2]
- 大頂堆滿足： Key[i] >= Key[2i+1] && key >= key[2i+2]
怎么理解呢，其實很簡單，顧名思義，大頂堆最大的元素在跟節點，堆的性質決定了大頂堆中節點一定大于等于其子節點，反之，小頂堆的最小元素在根節點，我們來看看大頂堆和小頂堆的示意圖:
堆排序基本思想及步驟
堆排序有以下幾個核心的步驟：
- 將待排序的陣列初始化為大頂堆，該程序即建堆，
- 將堆頂元素與最后一個元素進行交換，除去最后一個元素外可以組建為一個新的大頂堆，
- 由于第二部堆頂元素跟最后一個元素交換后，新建立的堆不是大頂堆，需要重新建立大頂堆，重復上面的處理流程，直到堆中僅剩下一個元素，
假設我們有一個待排序的陣列 arr = [4, 6, 7, 2, 9, 8, 3, 5]， 我們把這個陣列構造成為一個二叉樹，如下圖：
問：此時我們需要把這個完全二叉樹構造成一個大頂堆，怎么構造呢？
答：一個很好的方法是遍歷二叉樹的非葉子節點自下往上的構造大頂堆，針對每個非葉子節點，都跟它的左右子節點比較，把最大的值換到這個子樹的父節點，
問：為什么要從非葉子節點開始，而不是從最后一個節點開始？
答：因為葉子節點下面沒有子節點了，就沒必要操作了，
問：為什么要從下往上而不是從上往下遍歷非葉子節點？
答：我們從下面開始遍歷調整每個節點成為它左右節點的最大值，那么一直往上的話，最后根節點一定是最大的值；但是如果我們從上往下，上面滿足了大頂堆，下面不滿足，調整后，上面可能又不滿足了，所以從下往上是最好的方案，
那么我們構造的大頂堆的代碼就很明顯了：
# 構造大頂堆，從非葉子節點開始倒序遍歷，因此是l//2 -1 就是最后一個非葉子節點
l = len(arr)
for i in range(l//2-1, -1, -1):
build_heap()
# 遍歷針對每個非葉子節點構造大頂堆
看我們的例子，非葉子節點有2, 8, 6, 4， 我們從最后一個非葉子節點，也就是5開始遍歷構造大頂堆，2 跟 5 比較，5比較大，所以把 arr[3]和arr[7]從陣列中交換一下位置，那么就完成第一個非葉子節點的置換，下面的節點繼續交換
此時9跟4交換后，4這個節點下面的樹就不是不符合大頂堆了，所以要針對4這個節點跟它的左右節點再次比較，置換成較大的值，4跟左右子節點比較后，應該跟6交換位置，
那么至此，整個二叉樹就是一個完完整整的大頂堆了，每個節點都不小于左右子節點，
此時我們把堆的跟節點，即陣列最大值9跟陣列最后一個元素2交換位置，那么9就是排好序的放在了陣列最后一個位置
2到了跟節點后，新的堆不滿足大頂堆，我們需要重復上面的步驟，重新構造大頂堆，然后把大頂堆根節點放到二叉樹后面作為排好序的陣列放好，就這樣利用大頂堆一個一個的數字排好序，
值得注意的一個地方是，上面我們把9和2交換位置后，2處于二叉樹根節點，2需要跟右子樹8交換位置，交換完位置后，右子樹需要重新遞回調整大頂堆，但是左子樹6這邊，已經是滿足大頂堆屬性，因為不需要再操作，
我們再看看堆排序的一個直觀的動圖吧：
代碼實作：
class Solution(object):
def heap_sort(self, nums):
i, l = 0, len(nums)
self.nums = nums
# 構造大頂堆，從非葉子節點開始倒序遍歷，因此是l//2 -1 就是最后一個非葉子節點
for i in range(l//2-1, -1, -1):
self.build_heap(i, l-1)
# 上面的回圈完成了大頂堆的構造，那么就開始把根節點跟末尾節點交換，然后重新調整大頂堆
for j in range(l-1, -1, -1):
nums[0], nums[j] = nums[j], nums[0]
self.build_heap(0, j-1)
return nums
def build_heap(self, i, l):
"""構建大頂堆"""
nums = self.nums
left, right = 2*i+1, 2*i+2 ## 左右子節點的下標
large_index = i
if left <= l and nums[i] < nums[left]:
large_index = left
if right <= l and nums[left] < nums[right]:
large_index = right
# 通過上面跟左右節點比較后，得出三個元素之間較大的下標，如果較大下表不是父節點的下標，說明交換后需要重新調整大頂堆
if large_index != i:
nums[i], nums[large_index] = nums[large_index], nums[i]
self.build_heap(large_index, l)
堆排序復雜度
時間復雜度， 包括兩個方面：
- 初始化建堆程序時間：O(n)
- 更改堆元素后重建堆時間：O(nlogn)，回圈 n -1 次，每次都是從根節點往下回圈查找，所以每一次時間是 logn，總時間：logn(n-1) = nlogn - logn ，所以復雜度是 O(nlogn)
時間復雜度：O(nlogn)
空間復雜度： 因為堆排序是就地排序，空間復雜度為常數：O(1)
堆排序的應用：TopK演算法
面試中經常考的一個面試題就是，如果在海量資料中找出最大的100個數字，看到這個問題，可能大家首先會想到的是使用高效排序演算法，比如快排，對這些資料排序，時間復雜度是O(nlogn)，然后取出最大的100個數字，但是如果資料量很大，一個機器的記憶體不足以一次過讀取這么多資料，就不能使用這個方法了，
不使用分布式機器計算，使用一個機器也能找出TopK的經典演算法就是使用堆排序了，具體方法是：
維護一個大小為 K 的小頂堆，依次將資料放入堆中，當堆的大小滿了的時候，只需要將堆頂元素與下一個數比較：
- 如果小于堆頂元素，則直接忽略，比較下一個元素；
- 如果大于堆頂元素，則將當前的堆頂元素拋棄，并將該元素插入堆中，遍歷完全部資料，Top K 的元素也自然都在堆里面了，
整個操作中，遍歷陣列需要O(n)的時間復雜度，每次調整小頂堆的時間復雜度是O(logK)，加起來就是 O(nlogK) 的復雜度，如果 K 遠小于 n 的話， O(nlogK) 其實就接近于 O(n) 了，甚至會更快，因此也是十分高效的，
總結
堆排序有以下幾個核心的步驟：
- 將待排序的陣列初始化為大頂堆，該程序即建堆，
- 將堆頂元素與最后一個元素進行交換，除去最后一個元素外可以組建為一個新的大頂堆，
- 由于第二部堆頂元素跟最后一個元素交換后，新建立的堆不是大頂堆，需要重新建立大頂堆，重復上面的處理流程，直到堆中僅剩下一個元素，
最后
文章如果對你有識訓，可以收藏轉發，這也是對我寫作的肯定！另外可以關注我公眾號「碼農富哥」 ，我會持續輸出Python，服務端架構，計算機基礎（MySQL， Linux，TCP/IP）的 原創 文章
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/93582.html
標籤：其他
上一篇：Lua實作的八皇后問題