Python中的堆排序|极客笔记

Python中的堆排序

堆排序与选择排序非常相似，我们在其中找到最大的元素并将其放置在最后。它是基于比较排序算法，其在二叉堆数据结构上工作。它是高效排序算法的最佳示例。

什么是堆排序

堆排序是一种高效且流行的排序算法。堆排序的概念是逐个地将堆部分的元素”消除”并将它们插入到已排序部分的列表中。在学习更多关于堆排序算法之前，让我们讨论堆数据结构。

它是一种原地算法，这意味着使用了固定数量的内存来存储已排序的列表，或者内存大小不依赖于初始列表的大小。

例如 – 我们不需要额外的内存堆栈来存储已排序数组，也不需要递归调用堆栈。堆排序算法通常使用第二个数组来排序固定的值。这个过程快速、简单、自然且易于实现。

另一方面，堆排序是不稳定的，这意味着它不会保持具有相等值的元素的比较顺序。它可以快速排序原始类型，如整数和字符，但在处理复杂类型和对象时会有问题。

让我们通过以下示例来理解：

我们有一个自定义类”Student”，具有属性”age”和”name”，以及该类的多个对象在一个数组中，包括一个名为”Thomas”年龄为”20″的学生，还有一个名为”Peter”的学生，年龄也为”20″。

如果我们按年龄对数组中的人进行排序，那么不能保证”Thomas”会出现在已排序数组中的”Peter”之前。虽然可以定义顺序，但不能保证。

堆数据结构

堆数据结构是满足堆属性的完全二叉树，也被称为二叉堆。

完全二叉树满足以下属性：

每一层都应该填充。
所有节点尽量靠左。

Python中的堆排序

如图所示的堆中，但它没有排序。我们将不会深入研究本文，因为我们的重点是解释堆排序算法而不是堆。在堆排序中，下一个最小的元素始终是第一个元素。

堆树可以是两种类型 – 最小堆和最大堆。最小堆保留最大元素的记录。最大堆跟踪最大元素。堆主要支持以下操作 – 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]

解释

在上面的代码中，我们导入了 heapq 模块，其中包含 heappop() 和 heappush() 方法。我们创建了 Heapsort Heapsort() 方法，它将list1作为参数。通过for循环迭代list1，并将元素添加到空堆中。我们使用while循环并将排序后的元素添加到 空排序 中。

我们调用了 Heapsort Heapsort() 函数并传入一个列表。它返回排序后的列表。

排序自定义对象

堆排序对于预定义的数据类型很有用，但是对于处理用户定义的数据类型（如类对象）来说更加复杂。在本节中，我们将对自定义对象进行排序。

正如我们所见，我们的实现依赖于内置方法。Python提供了以下方法。

heapq.nlargest(n, iterable, *key = None) – 这个方法用于从由可迭代对象定义的数据集中得到包含n个最大元素的列表。
heapq.nsmallest(n, iterable, *key = None) – 这个方法用于从由可迭代对象定义的数据集中得到包含n个最小元素的列表。

让我们了解一下自定义对象的以下实现。

示例

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

我们已经按年份对对象进行了排序。