本篇文章將介紹堆排序算法在 Python 中的實(shí)現(xiàn)。

Python中的堆排序算法

堆排序是一種強(qiáng)大的算法，用于在 Python 中對(duì)數(shù)組和列表進(jìn)行排序。 它很受歡迎，因?yàn)樗浅？欤⑶也幌窈喜⑴判蚝涂焖倥判蚰菢诱加萌魏晤~外空間。

堆排序的時(shí)間復(fù)雜度是 O(n*log(n)) 。

堆排序是一種就地算法，它不再創(chuàng)建任何數(shù)據(jù)結(jié)構(gòu)來(lái)保存數(shù)據(jù)的中間狀態(tài)。 相反，它對(duì)我們的原始數(shù)組進(jìn)行了更改。

因此，當(dāng)數(shù)據(jù)非常大時(shí)，這為我們節(jié)省了大量空間。

該算法唯一的缺點(diǎn)是它非常不穩(wěn)定。 如果我們的數(shù)組中有多個(gè)元素在不同索引處具有相同的值，則它們的位置將在排序時(shí)發(fā)生變化。

堆排序算法的工作原理是遞歸地創(chuàng)建一個(gè)最小或最大堆，取出根節(jié)點(diǎn)，將其放在我們數(shù)組中的第一個(gè)未排序索引處，并將最后一個(gè)堆元素轉(zhuǎn)換為根節(jié)點(diǎn)。

這個(gè)過(guò)程遞歸重復(fù)，直到我們?cè)诙阎辛粝乱粋€(gè)節(jié)點(diǎn)。 最后，最后一個(gè)堆元素被放置在我們數(shù)組的最后一個(gè)索引處。

如果我們想一想，這個(gè)過(guò)程類(lèi)似于選擇排序算法，因?yàn)槲覀內(nèi)∽畲笾祷蜃钚≈挡⑺鼈兎旁谝雅判驍?shù)組的頂部。

在 Python 中實(shí)現(xiàn)堆排序算法

我們將首先了解實(shí)現(xiàn) build_heap() 函數(shù)，該函數(shù)采用原始數(shù)組、數(shù)組的長(zhǎng)度和父節(jié)點(diǎn)的索引。 在這里，如果我們查看一個(gè)數(shù)組，最后一個(gè)父節(jié)點(diǎn)的索引位于我們數(shù)組內(nèi)的 (n//2 - 1) 處。

類(lèi)似地，該特定父級(jí)的左孩子的索引為 2*parent_index + 1 ，右孩子的索引為 2*parent_index + 2 。

在這個(gè)例子中，我們?cè)噲D創(chuàng)建一個(gè)最大堆。 這意味著每個(gè)父節(jié)點(diǎn)都需要大于其子節(jié)點(diǎn)。

為此，我們將從最后一個(gè)父節(jié)點(diǎn)開(kāi)始，向上移動(dòng)到堆的根節(jié)點(diǎn)。 如果我們想創(chuàng)建一個(gè)最小堆，我們希望所有父節(jié)點(diǎn)都小于它們的子節(jié)點(diǎn)。

此 build_heap() 函數(shù)將檢查左或右子節(jié)點(diǎn)是否大于當(dāng)前父節(jié)點(diǎn)，并將最大節(jié)點(diǎn)與父節(jié)點(diǎn)交換。

該函數(shù)遞歸地調(diào)用自身，因?yàn)槲覀兿Ｍ麑?duì)堆中的所有父節(jié)點(diǎn)遞增地重復(fù)之前的過(guò)程。

以下代碼片段演示了上述 built_heap() 函數(shù)在 Python 中的有效實(shí)現(xiàn)。

def build_heap(arr, length, parent_index):
    largest_index = parent_index
    left_index = 2 * parent_index + 1
    right_index = 2 * parent_index + 2
    if left_index < length and arr[parent_index] < arr[left_index]:
        largest_index = left_index
    if right_index < length and arr[largest_index] < arr[right_index]:
        largest_index = right_index
    if largest_index != parent_index:
        arr[parent_index],arr[largest_index] = arr[largest_index],arr[parent_index]
        build_heap(arr, length, largest_index)

現(xiàn)在，我們有一個(gè)函數(shù)，它獲取數(shù)組中的最大值并將其放在堆的根部。 我們需要一個(gè)函數(shù)來(lái)獲取未排序的數(shù)組，調(diào)用 build_heap() 函數(shù)并從堆中提取元素。

以下代碼片段演示了 heapSort() 函數(shù)在 Python 中的實(shí)現(xiàn)。

def heapSort(arr):
    length = len(arr)
    for parent_index in range(length // 2 - 1, -1, -1):
        build_heap(arr, length, parent_index)
    for element_index in range(length-1, 0, -1):
        arr[element_index], arr[0] = arr[0], arr[element_index]
        build_heap(arr, element_index, 0)

我們?cè)跀?shù)組中逐步調(diào)用每個(gè)父節(jié)點(diǎn)的 build_heap() 函數(shù)。 請(qǐng)注意，我們將 length//2-1 作為起始索引，-1 作為結(jié)束索引，步長(zhǎng)為 -1。

這意味著我們從最后一個(gè)父節(jié)點(diǎn)開(kāi)始，遞減索引 1，直到到達(dá)根節(jié)點(diǎn)。

第二個(gè) for 循環(huán)從我們的堆中提取元素。 它也從最后一個(gè)索引開(kāi)始，并在我們數(shù)組的第一個(gè)索引處停止。

我們?cè)诖搜h(huán)中交換數(shù)組的第一個(gè)和最后一個(gè)元素，并通過(guò)傳遞 0 作為根索引對(duì)新排序的數(shù)組執(zhí)行 build_heap() 函數(shù)。

現(xiàn)在，我們已經(jīng)編寫(xiě)了用 Python 實(shí)現(xiàn)堆排序的程序。 是時(shí)候?qū)?shù)組進(jìn)行排序并測(cè)試上面編寫(xiě)的代碼了。

arr = [5, 3, 4, 2, 1, 6]
heapSort(arr)
print("Sorted array :", arr)

輸出:

Sorted array : [1, 2, 3, 4, 5, 6]

如我們所見(jiàn)，我們的數(shù)組已完全排序。 這意味著我們的代碼工作得很好。

如果我們想按降序排序，我們可以創(chuàng)建一個(gè)最小堆而不是上面實(shí)現(xiàn)的最大堆。

本文不會(huì)解釋最小堆，因?yàn)樗呀?jīng)在本教程的開(kāi)頭討論了最小堆是什么。

我們的程序以下列方式工作。 以下塊顯示了我們的數(shù)組在代碼執(zhí)行的每個(gè)階段的狀態(tài)。

Original Array [5, 3, 4, 2, 1, 6] # input array
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 1
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 2
Building Heap [6, 3, 5, 2, 1, 4] # after build_heap() pass 3
Extracting Elements [6, 3, 5, 2, 1, 4] # before swapping and build_heap pass 1
Extracting Elements [5, 3, 4, 2, 1, 6] # before swapping and build_heap pass 2
Extracting Elements [4, 3, 1, 2, 5, 6] # before swapping and build_heap pass 3
Extracting Elements [3, 2, 1, 4, 5, 6] # before swapping and build_heap pass 4
Extracting Elements [2, 1, 3, 4, 5, 6] # before swapping and build_heap pass 5
Sorted array : [1, 2, 3, 4, 5, 6] # after swapping and build_heap pass 5

build_heap() 函數(shù)執(zhí)行了 3 次，因?yàn)槲覀兊亩阎兄挥?3 個(gè)父節(jié)點(diǎn)。

之后，我們的元素提取階段獲取第一個(gè)元素，將其與最后一個(gè)元素交換，然后再次執(zhí)行 build_heap() 函數(shù)。 對(duì)長(zhǎng)度 - 1 重復(fù)此過(guò)程，我們的數(shù)組得到排序。

到此這篇關(guān)于Python 堆排序的文章就介紹到這了,更多相關(guān)Python 堆排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論