深刻理解堆和堆排序以及在 Python 中的应用

您是否也厌倦了需要很长时间才能处理大型数据集的缓慢、低效的排序算法？

是时候跟着icode9技术分享来看看堆排序了，这是一种高性能的排序算法，可以在O(Nlg(N))时间复杂度和O(1)空间复杂度上快速高效地对数据集进行排序。

在本文中，我们将深入探讨 Python 中的堆和堆排序，探索这种强大算法的内部工作原理，并学习如何逐步实现它。

堆简介：一种基于树的数据结构

堆是满足堆特性的完全二叉树，即树中每个节点的值大于或等于其子节点的值。

有两种类型的堆：

1. 最大堆：在最大堆中，每个节点的值都大于或等于其子节点的值，并且根节点在树中具有最大值。

2. 最小堆：在最小堆中，每个节点的值都小于或等于其子节点的值，并且根节点在树中具有最小值。

堆排序如何工作

堆排序是一种基于比较的排序算法，它使用堆数据结构对元素列表进行排序。它的工作原理是从输入列表构建一个堆，然后重复提取根元素（最大值或最小值）并将其放在排序列表的末尾。重复此过程，直到堆为空并且列表已完全排序。

简单来说，有两个步骤：

1. 构建堆

2. 从堆中提取元素

3.  

如何在 Python 中表示堆？

首先，我们需要知道如何在构建堆之前正确地表示它。

鉴于堆是一棵完全二叉树，我们可以直接使用 Python 列表来表示堆。

树的列表表示意味着真正的树在我们的脑海中。我们总是在真实代码中操作列表。

它之所以起作用，是因为列表和树之间存在以下特殊关系：

树的根始终是 index 处的元素0。

index 处节点的左孩子i存储在 index2i+1中，右孩子存储在 index2i+2中。

因此，我们总是可以通过列表的索引轻松访问树的节点。

例如，这是一个名为 的输入列表arr。

它的元素是[5, 2, 7, 1, 3]。

它代表一个原始的完全二叉树，我们需要将它转换为一个堆，如下所示：

1. 树的根是arr[0]

2. 根的左孩子是arr[2*0+1]，右孩子是arr[2*0+2]。

如何建堆？

从列表构建堆的过程称为 heapify。

原始列表已经是二叉树的表示（树在我们的脑海中），如上所示。我们需要做的是将原始树转换为堆。

由于最大堆和最小堆具有相似的思想。下面就说说如何建立最大堆吧。

思路是自下而上遍历二叉树的非叶子节点构造一个最大堆，对于每个非叶子节点，将其与其左右子节点进行比较，将最大值与父节点交换这个子树。

为什么从非叶节点而不是最后一个节点开始？

因为叶子节点下面没有子节点，所以不需要操作。

为什么从下往上遍历而不是从上往下遍历？

如果我们从底部往上走，肯定会将最大值放入根节点（类似于冒泡排序的思想）。

提取一个元素后如何更新堆？

把原来的链表转成堆后，剩下的就简单了。我们只需要反复提取堆的根元素，也就是最大/最小元素，放到需要返回的排序列表的末尾即可。

但是，我们需要做一件事——在提取根节点后更新整个堆。

它需要两个步骤：

用堆中的最后一个元素替换根节点：删除根节点（在最大堆中具有最大值或在最小堆中具有最小值）并将其替换为堆中的最后一个元素。

再次堆化整个堆。

在 Python 中实现堆排序

话不多说，让我们看看代码：

关键功能是heapify和heapify_node。它们用于从原始列表构建堆。

使用 Python 的 heapq 模块

幸运的是，我们不需要每次都实现构建堆的基本功能。Python 有一个名为heapq.

该heapq模块提供了处理堆的功能，包括：

heappush(heap, elem)：将一个元素压入堆中，保持堆属性。

heappop(heap)：从堆中弹出并返回最小的元素，保持堆属性。

heapify(x)：在线性时间内将常规列表就地转换为堆。

nlargest(k, iterable, key=None)：返回一个列表，其中包含指定迭代器中的 k 个最大元素并满足堆属性。

nsmallest(k, iterable, key=None)：返回一个列表，其中包含指定可迭代对象中的 k 个最小元素并满足堆属性。

heapq模块实现为堆队列，即优先级队列实现为堆。它是高效排序和搜索列表和其他可迭代对象的有用工具。

现在，让我们用它来做堆排序：

import heapq

def heap_sort ( arr ):
# 建立一个堆
heapq.heapify(arr)

# 从堆中逐一提取元素
sorted_arr = []
while arr:
sorted_arr.append(heapq.heappop(arr))

return sorted_arr

# 测试堆排序函数
arr = [ 5 , 21 , 207 , 19 , 3 ]
print (heap_sort(arr))
# 输出：[3, 5, 19, 21, 207]

简单又优雅，不是吗？

本站声明：
1. iCode9 技术分享网（下文简称本站）提供的所有内容，仅供技术学习、探讨和分享；

2. 关于本站的所有留言、评论、转载及引用，纯属内容发起人的个人观点，与本站观点和立场无关；

3. 关于本站的所有言论和文字，纯属内容发起人的个人观点，与本站观点和立场无关；

4. 本站文章均是网友提供，不完全保证技术分享内容的完整性、准确性、时效性、风险性和版权归属；如您发现该文章侵犯了您的权益，可联系我们第一时间进行删除；

5. 本站为非盈利性的个人网站，所有内容不会用来进行牟利，也不会利用任何形式的广告来间接获益，纯粹是为了广大技术爱好者提供技术内容和技术思想的分享性交流网站。