八十三、經(jīng)典排序算法之堆排序

「@Author：Runsen」

編程的本質(zhì)來(lái)源于算法，而算法的本質(zhì)來(lái)源于數(shù)學(xué)，編程只不過(guò)將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

堆通常是一個(gè)可以被看做一棵樹(shù)(完全)的數(shù)組對(duì)象。且總是滿(mǎn)足以下規(guī)則：

• 堆是一棵完全二叉樹(shù)
• 節(jié)點(diǎn)總是大于(或小于)它的孩子節(jié)點(diǎn)。

因此，根據(jù)第二個(gè)特性，就把二叉堆分為大頂堆（或叫最大堆），和小頂堆（或叫最小堆）。

在上圖中，1 2 是大頂堆 ，3 4 是小頂堆。判斷是不是堆的條件：「從根結(jié)點(diǎn)到任意結(jié)點(diǎn)路徑上結(jié)點(diǎn)序列的有序性！大頂堆和小頂堆判斷序列是順序還是逆序！」

Python并沒(méi)有提供“堆”這種數(shù)據(jù)類(lèi)型，它是直接把列表當(dāng)成堆處理的。Python提供的heapq包中有一些函數(shù)，提供執(zhí)行堆操作的工具函數(shù)

>>>?import?heapq
>>>?heapq.__all__
['heappush',?'heappop',?'heapify',?'heapreplace',?'merge',?'nlargest',?'nsmallest',?'heappushpop']

堆排序

往堆中插入一個(gè)元素后，我們就需要進(jìn)行調(diào)整，讓其重新滿(mǎn)足堆的特性，這個(gè)過(guò)程叫做堆化（heapify）。

那么堆排序的基本思路是怎么樣的呢？

1. 將待排序序列構(gòu)建成一個(gè)堆 H[0……n-1]，根據(jù)（升序降序需求）選擇大頂堆或小頂堆；

2. 把堆首（最大值）和堆尾互換；

3. 順著節(jié)點(diǎn)所在的路徑，向上或者向下，對(duì)比，然后交換，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置；

下面舉個(gè)例子（資源來(lái)自王爭(zhēng)算法），比如在上面的大頂堆中添加數(shù)據(jù)22。

堆化非常簡(jiǎn)單，就是順著節(jié)點(diǎn)所在的路徑，向上或者向下，對(duì)比，然后交換。

堆排序的刪除操作，這里一般指的是堆頂元素，當(dāng)我們刪除堆頂元素之后，就需要把第二大的元素放到堆頂，那第二大元素肯定會(huì)出現(xiàn)在左右子節(jié)點(diǎn)中。

然后我們?cè)俚貏h除第二大節(jié)點(diǎn)，以此類(lèi)推，直到葉子節(jié)點(diǎn)被刪除。但是這樣會(huì)產(chǎn)生一個(gè)數(shù)組空洞的問(wèn)題。

因此，這里面又個(gè)技巧，就是刪除堆頂元素的時(shí)候，不能直接刪除，要用堆頂元素和最后一個(gè)元素做交換，然后根據(jù)堆的特點(diǎn)調(diào)整堆，直到滿(mǎn)足條件。

排序的過(guò)程就是每次待排序的序列長(zhǎng)度減去1再執(zhí)行這兩步。

下面給出通過(guò)Python中的heapq模塊實(shí)現(xiàn)的堆排序簡(jiǎn)單代碼。

from?heapq?import?heappop,?heappush

def?heap_sort(array):
????heap?=?[]
????for?element?in?array:
????????heappush(heap,?element)

????ordered?=?[]

????while?heap:
????????ordered.append(heappop(heap))
????return?ordered

array?=?[13,?21,?15,?5,?26,?4,?17,?18,?24,?2]
print(heap_sort(array))
#?[2,?4,?5,?13,?15,?17,?18,?21,?24,?26]

如果不使用heapq模塊，對(duì)于推排序需要了解堆排序中的建堆過(guò)程。

將數(shù)組原地建成一個(gè)堆。不借助另一個(gè)數(shù)組，就在原數(shù)組上操作。建堆的過(guò)程，有兩種思路。

第一種建堆思路的處理過(guò)程是從前往后處理數(shù)組數(shù)據(jù)，并且每個(gè)數(shù)據(jù)插入堆中時(shí)，都是從下往上堆化。而第二種實(shí)現(xiàn)思路，是從后往前處理數(shù)組，并且每個(gè)數(shù)據(jù)都是從上往下堆化。

補(bǔ)充：利用層序遍歷(遍歷方式還有前中后)映射到數(shù)組后，假設(shè)樹(shù)或子樹(shù)的根節(jié)點(diǎn)為arr[root],則其對(duì)應(yīng)的子節(jié)點(diǎn)分別為arr[root*2+1],arr[root*2+2]。

也就是如果節(jié)點(diǎn)的下標(biāo)是 i，那左子節(jié)點(diǎn)的下標(biāo)就是 2?i+1，右子節(jié)點(diǎn)的下標(biāo)就是 2?i+2，父節(jié)點(diǎn)的下標(biāo)就是 。

def?heap_sort(array):
????n?=?len(array)
????#?從尾部開(kāi)始建堆，這樣保證子節(jié)點(diǎn)有序
????for?i?in?range((n-1)//2,?-1,?-1):
????????_shift(array,?n,?i)
????#?依次把堆頂元素交換到最后，重建堆頂（堆不包含剛交換的最大元素）
????for?i?in?range(n-1,?0,?-1):
????????array[0],?array[i]?=?array[i],?array[0]
????????_shift(array,?i,?0)
????return?array

#?重建堆頂元素 n：堆元素個(gè)數(shù)，i：堆建頂位置
def?_shift(array,?n,?i):
????#?如果沒(méi)有子節(jié)點(diǎn)，直接返回
????if?i*2+1?>=?n:
????????return
????#?取最大子節(jié)點(diǎn)位置
????maxsub?=?i*2+2?if?i*2+2?and?array[i*2+1]?<=?array[i*2+2]?else?i*2+1
????#?如果節(jié)點(diǎn)小于最大子節(jié)點(diǎn)，交換元素，遞歸以子節(jié)點(diǎn)為堆頂重建
????if?array[i]?????????array[i],?array[maxsub]?=?array[maxsub],?array[i]
????????_shift(array,?n,?maxsub)

if?__name__?==?'__main__':
????array?=?[13,?21,?15,?5,?26,?4,?17,?18,?24,?2]
????print(heap_sort(array))
????
#?[2,?4,?5,?13,?15,?17,?18,?21,?24,?26]

堆排序不是穩(wěn)定的排序算法，因?yàn)樵谂判虻倪^(guò)程，存在將堆的最后一個(gè)節(jié)點(diǎn)跟堆頂節(jié)點(diǎn)互換的操作，所以就有可能改變值相同數(shù)據(jù)的原始相對(duì)順序。堆排序整體的時(shí)間復(fù)雜度是 。

本文已收錄 GitHub，傳送門(mén)~^[1] ，里面更有大廠(chǎng)面試完整考點(diǎn)，歡迎 Star。

參考資料