堆数据结构的新功能。
尝试从列表创建堆。
li = [5, 7, 9, 1, 3]
heapq.heapify(li)
堆积后,输出为
[1, 3, 9, 7, 5]
为什么是这个订单?
我认为对于最小优先级堆,元素应该从最小到最大排序,即heapq.heapify(li)
应该与li.sort()
相同
有人可以帮助我理解吗?
堆实际上的排序方式与列表的排序方式不同。Python没有唯一的堆数据结构,并且使用带有堆操作的列表,这可能是你们中一些人混淆的根源。排序(最低优先级(堆是满足"堆条件"的堆,以便任何子节点都大于其父节点。这并不意味着平展表示将按顺序排列。
在展平之前,您的示例将如下所示:
1
/
3 9
/
7 5
每个节点最多获得 2 个子节点,并且始终从左到右添加子节点,直到行已满。然后通过连接以下行来创建平面表示:[1] + [3, 9] + [7, 5]
将堆视为树更容易:
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 + 1
分别是计算位置i
处节点的左子节点和右子节点的公式:
+--+--+
| v v
[1, 3, 9, 7, 5]
| ^ ^
+-----+--+
(可以为从 0 开始的数组指定这些属性,但使用从 1 开始的数组考虑起来更简单。
这样的列表是堆有序的(这比排序弱,因为所有排序的列表也是堆排序的(,并且允许有效地实现标准堆方法。
事实上堆排序是一种半排列算法。 主要思想是每个父级都应该小于或等于其子级(最小堆排序(。 所以我们知道第一个元素是最小的。当我们弹出堆的第一个元素时,下一个最小的元素将取代它。
有关更多信息,请参阅以下喜好:
堆排序
维基百科