堆基本概念

堆排序是一個(gè)很重要的排序算法，它是高效率的排序算法，復(fù)雜度是O(nlogn)，堆排序不僅是面試進(jìn)場(chǎng)考的重點(diǎn)，而且在很多實(shí)踐中的算法會(huì)用到它，比如經(jīng)典的TopK算法、小頂堆用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列。

堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆實(shí)際上是一個(gè)完全二叉樹結(jié)構(gòu)。
問：那么什么是完全二叉樹呢？
答：假設(shè)一個(gè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹。

完全二叉樹

我們知道堆是一個(gè)完全二叉樹了，那么堆又分兩種堆：大頂堆 和 小頂堆
它們符合一個(gè)重要的性質(zhì)：

• 小頂堆滿足： Key[i] <= key[2i+1] && Key[i] <= key[2i+2]
• 大頂堆滿足： Key[i] >= Key[2i+1] && key >= key[2i+2]

怎么理解呢，其實(shí)很簡(jiǎn)單，顧名思義，大頂堆最大的元素在跟節(jié)點(diǎn)，堆的性質(zhì)決定了大頂堆中節(jié)點(diǎn)一定大于等于其子節(jié)點(diǎn)，反之，小頂堆的最小元素在根節(jié)點(diǎn)。我們來(lái)看看大頂堆和小頂堆的示意圖:

大頂堆和小頂堆

堆排序基本思想及步驟

堆排序有以下幾個(gè)核心的步驟：

1. 將待排序的數(shù)組初始化為大頂堆，該過(guò)程即建堆。
2. 將堆頂元素與最后一個(gè)元素進(jìn)行交換，除去最后一個(gè)元素外可以組建為一個(gè)新的大頂堆。
3. 由于第二部堆頂元素跟最后一個(gè)元素交換后，新建立的堆不是大頂堆，需要重新建立大頂堆。重復(fù)上面的處理流程，直到堆中僅剩下一個(gè)元素。

假設(shè)我們有一個(gè)待排序的數(shù)組 arr = [4, 6, 7, 2, 9, 8, 3, 5]， 我們把這個(gè)數(shù)組構(gòu)造成為一個(gè)二叉樹，如下圖：

數(shù)組構(gòu)造成完全二叉樹

問：此時(shí)我們需要把這個(gè)完全二叉樹構(gòu)造成一個(gè)大頂堆，怎么構(gòu)造呢？
答：一個(gè)很好的方法是遍歷二叉樹的非葉子節(jié)點(diǎn)自下往上的構(gòu)造大頂堆，針對(duì)每個(gè)非葉子節(jié)點(diǎn)，都跟它的左右子節(jié)點(diǎn)比較，把最大的值換到這個(gè)子樹的父節(jié)點(diǎn)。

問：為什么要從非葉子節(jié)點(diǎn)開始，而不是從最后一個(gè)節(jié)點(diǎn)開始？
答：因?yàn)槿~子節(jié)點(diǎn)下面沒有子節(jié)點(diǎn)了，就沒必要操作了。

問：為什么要從下往上而不是從上往下遍歷非葉子節(jié)點(diǎn)？
答：我們從下面開始遍歷調(diào)整每個(gè)節(jié)點(diǎn)成為它左右節(jié)點(diǎn)的最大值，那么一直往上的話，最后根節(jié)點(diǎn)一定是最大的值；但是如果我們從上往下，上面滿足了大頂堆，下面不滿足，調(diào)整后，上面可能又不滿足了，所以從下往上是最好的方案。

那么我們構(gòu)造的大頂堆的代碼就很明顯了：

# 構(gòu)造大頂堆，從非葉子節(jié)點(diǎn)開始倒序遍歷，因此是l//2 -1 就是最后一個(gè)非葉子節(jié)點(diǎn)
l = len(arr)
for i in range(l//2-1, -1, -1): 
     build_heap()
     # 遍歷針對(duì)每個(gè)非葉子節(jié)點(diǎn)構(gòu)造大頂堆

看我們的例子，非葉子節(jié)點(diǎn)有2, 8, 6, 4， 我們從最后一個(gè)非葉子節(jié)點(diǎn)，也就是5開始遍歷構(gòu)造大頂堆，2 跟 5 比較，5比較大，所以把 arr[3]和arr[7]從數(shù)組中交換一下位置，那么就完成第一個(gè)非葉子節(jié)點(diǎn)的置換。下面的節(jié)點(diǎn)繼續(xù)交換

此時(shí)9跟4交換后，4這個(gè)節(jié)點(diǎn)下面的樹就不是不符合大頂堆了，所以要針對(duì)4這個(gè)節(jié)點(diǎn)跟它的左右節(jié)點(diǎn)再次比較，置換成較大的值，4跟左右子節(jié)點(diǎn)比較后，應(yīng)該跟6交換位置。

那么至此，整個(gè)二叉樹就是一個(gè)完完整整的大頂堆了，每個(gè)節(jié)點(diǎn)都不小于左右子節(jié)點(diǎn)。
此時(shí)我們把堆的跟節(jié)點(diǎn)，即數(shù)組最大值9跟數(shù)組最后一個(gè)元素2交換位置，那么9就是排好序的放在了數(shù)組最后一個(gè)位置

2到了跟節(jié)點(diǎn)后，新的堆不滿足大頂堆，我們需要重復(fù)上面的步驟，重新構(gòu)造大頂堆，然后把大頂堆根節(jié)點(diǎn)放到二叉樹后面作為排好序的數(shù)組放好。就這樣利用大頂堆一個(gè)一個(gè)的數(shù)字排好序。

值得注意的一個(gè)地方是，上面我們把9和2交換位置后，2處于二叉樹根節(jié)點(diǎn)，2需要跟右子樹8交換位置，交換完位置后，右子樹需要重新遞歸調(diào)整大頂堆，但是左子樹6這邊，已經(jīng)是滿足大頂堆屬性，因?yàn)椴恍枰俨僮鳌?br> 我們?cè)倏纯炊雅判虻囊粋€(gè)直觀的動(dòng)圖吧：

堆排序動(dòng)圖過(guò)程

代碼實(shí)現(xiàn)：

class Solution(object):
    def heap_sort(self, nums):
        i, l = 0, len(nums)
        self.nums = nums
        # 構(gòu)造大頂堆，從非葉子節(jié)點(diǎn)開始倒序遍歷，因此是l//2 -1 就是最后一個(gè)非葉子節(jié)點(diǎn)
        for i in range(l//2-1, -1, -1): 
            self.build_heap(i, l-1)
        # 上面的循環(huán)完成了大頂堆的構(gòu)造，那么就開始把根節(jié)點(diǎn)跟末尾節(jié)點(diǎn)交換，然后重新調(diào)整大頂堆  
        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): 
        """構(gòu)建大頂堆"""
        nums = self.nums
        left, right = 2*i+1, 2*i+2 ## 左右子節(jié)點(diǎn)的下標(biāo)
        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
 
        # 通過(guò)上面跟左右節(jié)點(diǎn)比較后，得出三個(gè)元素之間較大的下標(biāo)，如果較大下表不是父節(jié)點(diǎn)的下標(biāo)，說(shuō)明交換后需要重新調(diào)整大頂堆
        if large_index != i:
            nums[i], nums[large_index] = nums[large_index], nums[i]
            self.build_heap(large_index, l)

堆排序復(fù)雜度

時(shí)間復(fù)雜度， 包括兩個(gè)方面：

1. 初始化建堆過(guò)程時(shí)間：O(n)
2. 更改堆元素后重建堆時(shí)間：O(nlogn)，循環(huán) n -1 次，每次都是從根節(jié)點(diǎn)往下循環(huán)查找，所以每一次時(shí)間是 logn，總時(shí)間：logn(n-1) = nlogn - logn ，所以復(fù)雜度是 O(nlogn)

時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度： 因?yàn)槎雅判蚴蔷偷嘏判?，空間復(fù)雜度為常數(shù)：O(1)

堆排序的應(yīng)用：TopK算法

面試中經(jīng)常考的一個(gè)面試題就是，如果在海量數(shù)據(jù)中找出最大的100個(gè)數(shù)字，看到這個(gè)問題，可能大家首先會(huì)想到的是使用高效排序算法，比如快排，對(duì)這些數(shù)據(jù)排序，時(shí)間復(fù)雜度是O(nlogn)，然后取出最大的100個(gè)數(shù)字。但是如果數(shù)據(jù)量很大，一個(gè)機(jī)器的內(nèi)存不足以一次過(guò)讀取這么多數(shù)據(jù)，就不能使用這個(gè)方法了。

不使用分布式機(jī)器計(jì)算，使用一個(gè)機(jī)器也能找出TopK的經(jīng)典算法就是使用堆排序了，具體方法是：

維護(hù)一個(gè)大小為 K 的小頂堆，依次將數(shù)據(jù)放入堆中，當(dāng)堆的大小滿了的時(shí)候，只需要將堆頂元素與下一個(gè)數(shù)比較：

• 如果小于堆頂元素，則直接忽略，比較下一個(gè)元素；

• 如果大于堆頂元素，則將當(dāng)前的堆頂元素拋棄，并將該元素插入堆中。遍歷完全部數(shù)據(jù)，Top K 的元素也自然都在堆里面了。

  
  
  
  

整個(gè)操作中，遍歷數(shù)組需要O(n)的時(shí)間復(fù)雜度，每次調(diào)整小頂堆的時(shí)間復(fù)雜度是O(logK)，加起來(lái)就是 O(nlogK) 的復(fù)雜度，如果 K 遠(yuǎn)小于 n 的話， O(nlogK) 其實(shí)就接近于 O(n) 了，甚至?xí)?，因此也是十分高效的?/p>

總結(jié)

堆排序有以下幾個(gè)核心的步驟：

1. 將待排序的數(shù)組初始化為大頂堆，該過(guò)程即建堆。
2. 將堆頂元素與最后一個(gè)元素進(jìn)行交換，除去最后一個(gè)元素外可以組建為一個(gè)新的大頂堆。
3. 由于第二部堆頂元素跟最后一個(gè)元素交換后，新建立的堆不是大頂堆，需要重新建立大頂堆。重復(fù)上面的處理流程，直到堆中僅剩下一個(gè)元素。

關(guān)于我

如果文章對(duì)你有收獲，可以收藏轉(zhuǎn)發(fā)，這會(huì)給我一個(gè)大大鼓勵(lì)喲！
另外可以關(guān)注我公眾號(hào)【碼農(nóng)富哥】 (coder2025)，我會(huì)持續(xù)輸出原創(chuàng)的算法，計(jì)算機(jī)基礎(chǔ)文章！