作者：Olivera Popovi?

翻譯：老齊

介紹

堆排序是高效排序算法的另一個例子，它的主要優點是，無論輸入數據如何，它的最壞情況運行時間都是O(n*logn)。

顧名思義，堆排序在很大程度上依賴于堆數據結構——優先級隊列的常見實現。

毫無疑問，堆排序是一種簡單的排序算法，而且與其他簡單實現相比，堆排序是更有效，也很常見。

堆排序

堆排序的工作原理是從堆逐個“移除”元素并將它們添加到已排序的數組里，在進一步解釋和重新訪問堆數據結構之前，我們應該了解堆排序本身的一些屬性。

它是一種原地算法（譯者注：in-place algorithm，多數翻譯為“原地算法”，少數也翻譯為“就地算法”。這種算法是使用小的、固定數量的額外內存空間來轉換資料的算法。），意味著它需要恒定數量的內存，即所需內存不取決于初始數組本身的大小，而取決于存儲該數組所需的內存。

例如，不需要原始數組的副本，也不需要遞歸和遞歸調用堆棧。最簡單的堆排序實現通常使用第二個數組來存儲排序后的值。我們將使用這種方法，因為它在代碼中更直觀、更易于實現，但它也是百分百的原地算法。

堆排序不穩定，意思是相等的值，并不會在同樣的相對位次上。對于整數、字符串等這些基本類型，不會出現這類問題，但當我們對復雜類型的對象排序時，可能會遇到。

例如，假設我們有一個自定義類Person帶有age和name屬性，在一個數組中幾個此類的實例對象，比如按順序出現19歲的名叫“Mike”的人和一個19歲的名叫“David”的人。

如果我們決定按年齡對這些人進行排序，就不能在排序數組中保證“Mike”會出現在“David”之前，即使他們在初始數組中是按這個順序出現的。“Mike”有可能出現在“David”之前，但不能保證百分之百如此。

堆數據結構

堆是計算機科學中最流行和最常用的一種數據結構——更不用說在軟件工程面試中非常流行了。

我們將討論跟蹤最小元素（最小堆）的堆，但它們也可以很容易地實現對最大元素（最大堆）的跟蹤。

簡單地說，最小堆是一種基于樹的數據結構，其中每個節點比其所有子節點都小。通常使用二叉樹。堆有三個基本操作——delete_minimum()、get_minimum()和add()。

每次，你只能刪除堆中的第一個元素，然后對其進行“重新排序”。在添加或刪除元素后，堆對自己會“重新排序”，以便最小的元素始終處于第一個位置。

注意：這絕不意味著堆是排序的數組。每個節點都小于其子節點這一事實不足以保證整個堆是按升序排列的。

我們來看一個關于堆的例子：

正如我們看到的，上面的例子確實符合堆的描述，但是沒有排序。我們不會詳細討論堆實現，因為這不是本文的重點。當在堆排序中使用堆數據結構時，我們所利用的堆數據結構的關鍵優勢是：下一個最小的元素始終是堆中的第一個元素。

實現

數組排序

譯者注： 作者在本文中并沒有嚴格區分Python中的列表和數組，而是將列表看做了數組，這對于列表中的元素是同一種類型的元素而言，無可厚非。對于排序，只有是同一種類型的元素，才有意義。

Python提供了創建和使用堆的方法，所以我們不必自己單獨為了實現它們去寫代碼了:

• heappush(list, item)：向堆中添加一個元素，然后對其重新排序，使其保持堆狀態。可用于空列表。
• heappop(list)：刪除第一個（最小的）元素并返回該元素。此操作之后，堆仍然是一個堆，因此我們不必調用heapify()。
• heapify(list)：將給定的列表變成一個堆。

現在我們知道了這些，堆排序的實現就相當簡單了：

from heapq import heappop, heappushdef heap_sort(array):heap = []for element in array:heappush(heap, element)ordered = []# While we have elements left in the heapwhile heap:ordered.append(heappop(heap))return orderedarray = [13, 21, 15, 5, 26, 4, 17, 18, 24, 2] print(heap_sort(array))

輸出

[2, 4, 5, 13, 15, 17, 18, 21, 24, 26]

如我們所見，堆數據結構的繁重工作已經完成，我們所要做的只是添加所需的所有元素并逐個刪除它們。它就像一臺硬幣計數機，根據輸入的硬幣的價值對它們進行分類，然后我們可以取出它們。

自定義對象排序

當使用自定義類時，事情會變得更加復雜。通常，為了使用我們的排序算法，建議不要重寫類中的比較運算符，而是建議重寫該算法，以便使用lambda函數比較。

但是，由于我們的實現依賴于內置堆方法，因此不能在這里這樣做。

Python確實提供了以下方法：

• heapq.nlargest(*n*, *iterable*, *key=None*)：返回一個列表，其中包含由iterable定義的數據集中的n個最大元素。
• heapq.nsmallest(*n*, *iterable*, *key=None*)：返回一個列表，其中包含由iterable定義的數據集中的n個最小元素。

我們可以使用它來簡單地獲取n = len(array)最大/最小元素，但是方法本身不使用堆排序，本質上等同于只調用sorted()方法。

我們留給自定義類的唯一解決方案是實際重寫比較運算符。遺憾的是，這使我們局限于對每個類只能進行一種比較。在我們的示例中，我們被局限于按年份對Movie對象進行排序。

但是，它確實讓我們演示了在自定義類上使用堆排序。我們來定義Movie類：

from heapq import heappop, heappushclass Movie:def __init__(self, title, year):self.title = titleself.year = yeardef __str__(self):return str.format("Title: {}, Year: {}", self.title, self.year)def __lt__(self, other):return self.year < other.yeardef __gt__(self, other):return other.__lt__(self)def __eq__(self, other):return self.year == other.yeardef __ne__(self, other):return not self.__eq__(other)

現在，讓我們稍微修改一下heap_sort()函數：

def heap_sort(array):heap = []for element in array:heappush(heap, element)ordered = []while heap:ordered.append(heappop(heap))return ordered

最后，讓我們實例化一些電影，將它們放入一個數組中，然后對它們進行排序：

movie1 = Movie("Citizen Kane", 1941) movie2 = Movie("Back to the Future", 1985) movie3 = Movie("Forrest Gump", 1994) movie4 = Movie("The Silence of the Lambs", 1991); movie5 = Movie("Gia", 1998)array = [movie1, movie2, movie3, movie4, movie5]for movie in heap_sort(array):print(movie)

輸出：

Title: Citizen Kane, Year: 1941 Title: Back to the Future, Year: 1985 Title: The Silence of the Lambs, Year: 1991 Title: Forrest Gump, Year: 1994 Title: Gia, Year: 1998

與其他排序算法的比較

堆排序被廣泛使用，主要原因是它的可靠性，盡管它經常被運行良好的“快速排序”法所超越（譯者注： 本文的微信公眾號“老齊教室”以系列文章，介紹各種排序算法，并且用Python語言實現，敬請關注）。

堆排序的主要優點是時間復雜度上的O(n*logn)上限以及安全性。Linux內核開發人員給出了使用堆排序而不是快速排序的以下理由：

堆排序的平均排序時間和最壞排序時間均為O(n*logn)，雖然qsort的平均速度快了20%，但不得不容忍O(n*n)的最壞可能情形和額外的內存支出，這使它不太適合在操作系統內核中使用。

此外，快速排序算法法在可預測的情況下表現不佳。并且，如果對內部實現有足夠的了解，你可能會意識到它造成的安全風險（主要是DDoS攻擊），因為不良的O(n^2)行為很容易被觸發。

經常被用來與堆排序比較的另一種算法是歸并排序算法（譯者注： 本微信公眾號也會刊發相關文章給予介紹，敬請關注），它們具有相同的時間復雜度。

歸并排序的優點是穩定、可并行運算，而堆排序兩者都做不到。

另一個注意事項是：即使復雜度相同，堆排序在大多數情況下也比歸并排序慢，因為堆排序具有較大的常數因子。

然而，堆排序比歸并排序更容易實現，因此當內存比速度更重要時，它是首選。

結論

正如我們所看到的，堆排序不像其他高效的通用算法那么流行，但是它的可預測行為（而不是不穩定的行為）使它成為一個很好的算法，適用于內存和安全性比稍快的運行速度更重要的場合。

實現和利用Python提供的內置功能是非常直觀的，我們實際上要做的就是將元素放在一個堆中并取出它們，就像對待硬幣計數器一樣。

原文鏈接：https://stackabuse.com/heap-sort-in-python/

★ 關注微信公眾號：老齊教室。讀深度文章，得精湛技藝，享絢麗人生。
”

總結

以上是生活随笔為你收集整理的堆排序不稳定的例子_【译】Python中的堆排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。