Python中的堆排序

堆排序与选择排序非常相似，我们找到最大（或最小）的元素并将其放置在末尾。它是一种基于比较的排序算法，它在二叉堆数据结构上工作。它是高效排序算法的一个很好的例子。

什么是堆排序？

堆排序是一种高效且流行的排序算法。堆排序的概念是逐个“删除”列表的堆部分中的元素，并插入到列表的已排序部分。在深入了解堆排序算法之前，让我们先讨论堆数据结构。

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

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

另一方面，堆排序是不稳定的，这意味着它不会保持具有相等值的元素的相对顺序。它可以快速对整数和字符等基本类型进行排序，但对于复杂类型和对象则存在问题。

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

我们有一个自定义类Student，具有age和name属性，以及数组中该类的几个对象，其中包括一个名为“Thomas”的“20”岁的学生，还有一个“20”岁的“Peter”，他们出现顺序相同。

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

堆数据结构

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

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

• 每一层都应填满。
• 所有节点都应尽可能靠左。

正如我们在上面的堆图像中看到的，但它没有排序。我们不会深入研究本文，因为我们的重点是解释堆排序算法，而不是堆。在堆排序中，下一个最小的元素总是第一个元素。

堆树可以是两种类型 - 最小堆和最大堆。最小堆存储最大元素。最大堆存储最小元素。堆主要支持以下操作 - delete_minimum()、get_minimum() 和 add()。

通过恢复堆，可以删除堆的第一个元素。这需要O(log N)时间，这非常有效。

实施

Python 提供了用于使用堆排序对元素进行排序的内置函数。这些函数如下所示。

• heappush(list, item) - 用于添加堆元素并对其进行重新排序。
• heappop(list) - 用于删除并返回堆中的元素。
• heapfy() - 用于将给定的列表转换为堆。

考虑以下堆排序的示例。

示例 -

输出

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

说明

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

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

排序自定义对象

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

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

• heapq.nlargest(*n*, *iterable*, *key = None) - 此方法用于从数据集（由可迭代对象定义）中获取包含 n 个最大元素的列表。
• heapq.nsmallest(*n*, *iterable*, *key = None) - 此方法用于从数据集（由可迭代对象定义）中获取包含 n 个最小元素的列表。

让我们通过以下自定义对象实现来理解这一点。

示例 -

输出

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) 情况。

现在我们将其与归并排序进行比较，归并排序所需的时间与堆排序相同。

归并排序更稳定且直观可并行化，而堆排序不具备这些优势。

此外，在大多数情况下，归并排序比堆排序更快，因为它们具有相同的时间复杂度。

相比之下，堆排序比归并排序更容易原地实现。

结论

堆排序并不那么流行和快速，但它比任何其他排序算法都更可预测。在内存和安全是优先考虑的情况下，倾向于选择此算法。

可以使用 Python 快速实现。我们需要将元素插入堆中，然后将它们取出。