Python 中的堆排序

堆排序與選擇排序完全相同，我們找到最大元素並將其放在末尾。它基於在二進制堆數據結構上工作的比較排序算法。這是高效排序算法的最佳示例。

什麼是堆排序？

堆排序是一種高效且流行的排序算法。堆排序的概念是從列表的堆部分逐一“消除”元素，將它們插入到列表的排序部分。在進一步了解堆排序算法之前，讓我們討論一下堆數據結構。

它是一種就地算法，這意味着使用固定數量的內存來存儲排序列表，或者內存大小不依賴於初步列表的大小。

例如- 我們不需要額外的內存棧來存儲排序後的數組，也不需要遞歸調用棧。heapsort 算法通常使用第二個數組排序固定值。這一過程快速、簡單、自然且易於實施。

另一方面，堆排序是不穩定的，這意味着它不維護具有相等值的元素的比較順序。它可以快速排序整數和字符等基本類型，但它對複雜類型和對象有問題。

讓我們通過下面的例子來理解它-

我們有一個自定義類學生帶有屬性年齡和名字，和該類的幾個對象在一個數組中，包括一個名為“托馬斯”年齡為“20”的學生，還有“彼得”年齡為 20 的以相同的順序出現。

如果我們按照年齡排序人的排列，那麼不能保證“托馬斯”會出現在排序後的排列中的“彼得”之前。可以定義順序，但不能保證。

堆數據結構

堆數據結構是一個完成堆屬性的完整二叉樹。它也被稱為二進制堆。

完整的二叉樹滿足以下屬性。

• 每一關都要填。
• 所有節點都儘可能靠左。

正如我們在上面的堆圖像中看到的，但是它沒有被排序。我們不會深入挖掘這篇文章，因為我們的重點是解釋 Heap 排序算法，而不是堆。在堆排序中，下一個最小的元素總是第一個元素。

堆樹可以是兩種類型-最小堆和最大樹。最小堆保存最大元素的記錄。最大堆跟蹤最大的元素。堆主要支持以下操作——delete _ minimum()，get_minimum()和 add()。

堆的第一個元素可以在恢復後刪除。需要 O(log N) 時間，那是高效的。

履行

Python 提供了使用堆排序排序元素的內置函數。功能如下。

• heappush(list，item) – 用於添加堆元素並重新排序。
• heappop(list) – 用於移除元素並返回元素。
• heapfy() – 用來把給定的列表變成堆。

考慮下面的堆排序示例。

示例-

from heapq import heappop, heappush

 def heapsort(list1):
     heap = []
     for ele in list1:
         heappush(heap, ele)

     sort = []

     # the elements are lift in the heap
     while heap:
         sort.append(heappop(heap))

     return sort

 list1 = [27, 21, 55, 15, 60, 4, 11, 17, 2, 87]
 print(heapsort(list1))

輸出:

[2, 4, 11, 15, 17, 21, 27, 55, 60, 87]

解釋

在上面的代碼中，我們已經導入了由heap PP()和 heappush() 方法組成的 heapq 模塊。我們創建了Heapsort Heapsort()方法，該方法以 list1 為參數。for循環遍歷列表 1，並將元素推送到空堆。我們使用 While循環，並將排序後的元素添加到空排序中。

我們調用了 Heapsort Heapsort () 函數，並傳遞了一個列表。它返回排序列表。

對自定義對象排序

堆排序對於預定義的數據類型很有用，但是處理用戶定義的數據類型(如類對象)更複雜。我們將在本節中排序自定義對象。

正如我們所看到的，我們的實現依賴於內置的方法。Python 提供了以下方法。

• *heapq . nlargetst( n ，iterable，key = None) -** 該方法用於從數據集中獲取具有n個最大元素的列表，由 iterable 定義。
• *heapq . nsmallast( n ，iterable，key = None) -** 該方法用於從數據集獲取n個最小元素的列表，該列表由 iterable 定義。

讓我們理解以下自定義對象的實現。

示例-

from heapq import heappop, heappush

 class Car:
     def __init__(self, model, year):
         self.model = model
         self.year = year

     def __str__(self):
         return str.format("Model Name: {}, Year: {}", self.model, self.year)

     def __lt__(self, other):
         return self.year < other.year

     def __gt__(self, other):
         return other.__lt__(self)

     def __eq__(self, other):
         return self.year == other.year

     def __ne__(self, other):
         return not self.__eq__(other)

 def heapsort(list1):
     heap = []
     for element in list1:
         heappush(heap, element)

     ordered = []

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

     return ordered

 car1 = Car("Renault", 2001)
 car2 = Car("Bentley", 2005)
 car3 = Car("Kia", 2014)
 car4 = Car("Maruti Suzuki", 1999);
 car5 = Car("Nano", 2012)

 list1 = [car1, car2, car3, car4, car5]

 for c in Heapsort Heapsort (list1):
     print(c)

輸出:

Model Name: Maruti Suzuki, Year: 1999
Model Name: Renault, Year: 2001
Model Name: Bentley, Year: 2005
Model Name: Nano, Year: 2012
Model Name: Kia, Year: 2014

我們已經根據年份對物品進行了分類。

堆排序與其他算法的比較

流行的快速排序算法之一也非常有效，但堆排序是合法使用的，因為它的可靠性。就時間複雜度而言，堆排序的主要好處是 O(nlogn) 上限。

堆排序算法在平均和最壞情況下都需要 O(nlogn)時間，而快速排序在平均情況下要快 20%。

快速排序算法在可預測的情況下會變得很慢。快速排序存在安全漏洞的可能性，因為犯規 O(n2)很容易被觸發。

現在我們比較歸併排序，它與堆排序花費相同的時間。

歸併排序穩定得多，直觀上是可並行的，而堆排序沒有這樣的優勢。

此外，歸併排序在大多數情況下比堆排序更快，因為它們具有相同的時間複雜性。

相比之下，HeapsortHeapsort 可以比 Marge sort 更快地就地實現。

結論

Heapsort 沒有那麼受歡迎，速度也沒有那麼快，但它比任何其他排序算法都更容易預測。在內存和安全性是優先考慮的情況下，此算法是首選。

可以使用 Python 快速實現。我們需要將元素插入堆中，然後取出它們。