提问人：user3075021 提问时间：5/31/2018 最后编辑：Patrick Haughuser3075021 更新时间：5/31/2018 访问量：2160
Python 中的堆顺序
heap order in python
问：
堆数据结构的新手。
尝试从列表创建堆。
li = [5, 7, 9, 1, 3]
heapq.heapify(li)
堆化后，输出为
[1, 3, 9, 7, 5]
为什么是这个订单？
我认为对于最小优先级堆，元素应该从最小到最大排序，即
应该与heapq.heapify(li)li.sort()
有人可以帮我理解吗？
答：
3赞
chepner
5/31/2018
#1
将堆视为树更容易：
1
3 9
7 5
其中每个节点都小于其任何一个子节点，但子节点的顺序无关紧要（将堆与二叉搜索树区分开来）。
一个完整的树通过按宽度优先顺序对节点进行编号来允许在数组中进行简单的嵌入，从根开始作为节点 1。
1(1)
3(2) 9(3)
7(4) 5(5)
通过这种嵌入，以下关系成立：
li[i] <= li[2*i]li[i] <= li[2*i + 1]
2*i和 分别是计算节点位置的左子项和右子项的公式：2*i + 1i
+--+--+
| v v
[1, 3, 9, 7, 5]
| ^ ^
+-----+--+
（您可以为从 0 开始的数组指定这些属性，但使用从 1 开始的数组更简单。
这样的列表是堆排序的（这比排序要弱，因为所有排序列表也是堆排序的），并且允许有效地实现标准堆方法。
评论
0赞
Norrius
5/31/2018
这样的列表是堆排序的，这与排序不同——我还注意到，通常的排序意味着堆排序，但不是相反。
5赞
Aaron
5/31/2018
#2
实际上，堆的排序方式与列表的排序方式不同。Python 没有唯一的堆数据结构，而是使用带有堆操作的列表，这可能是你们中一些人混淆的根源。排序（最小优先级）堆是满足“堆条件”的堆，使得任何子节点都大于其父节点。这并不意味着扁平化的表示形式是有序的。
在展平之前，您的示例将如下所示：
1
/ \
3 9
/ \
7 5
每个节点最多有 2 个子节点，并且始终从左到右添加子节点，直到行已满。然后，通过连接行来创建平面表示：[1] + [3, 9] + [7, 5]
1赞
Saeed Bolhasani
5/31/2018
#3
事实上，堆排序是一种半排列算法。主要思想是每个父级都应该小于或等于其子级（以最小堆排序）。
所以我们知道第一个元素是最小的。当我们弹出堆的第一个元素时，下一个最小的元素将取而代之。
有关详细信息，请参阅以下点赞：
评论
heapqheap[k]heap[2*k+1]heap[2*k+2]