python中的堆顺序

Question

新的堆数据结构。在

正在尝试从列表创建堆。在

li = [5, 7, 9, 1, 3]

heapq.heapify(li)

在heapipient之后，输出是

^{pr2}$

为什么要这么做？
我认为对于最小优先级堆，元素的顺序应该从min到max，即
heapq.heapify(li)应与li.sort()相同

有人能帮我理解吗？在

Answer 1

像一堆树一样容易看：

         1
     3      9
  7     5

其中每个节点都小于它的子节点，但子节点的顺序是不相关的（这将堆与二进制搜索树区分开来）。在

一个完整的树允许简单地嵌入数组中，方法是按照宽度优先的顺序对节点进行编号，从根开始作为节点1。在

^{pr2}$

通过这种嵌入，以下关系成立：

1. li[i] <= li[2*i]
2. li[i] <= li[2*i + 1]

2*i和2*i + 1是分别计算位于i的节点的左子节点和右子节点的公式：

 + + +
 |  v  v
[1, 3, 9, 7, 5]
    |     ^  ^
    +  -+ +

（可以为基于0的数组指定这些属性，但使用基于1的数组则更简单。）

这样的列表是堆排序的（这比排序的弱，因为所有排序的列表也是堆排序的），并允许标准堆方法有效地实现。在

Answer 2

堆实际上并不像列表那样排序。Python没有一个唯一的堆数据结构，它使用带有堆操作的列表，这可能是一些人感到困惑的根源。排序（最小优先级）堆是满足“堆条件”的堆，即任何子节点都大于其父节点。这并不意味着展平的表示是有序的。在

在展开之前，您的示例如下所示：

    1
   / \
  3   9
 / \
7   5

每个节点最多有2个子节点，并且子节点总是从左到右添加，直到行满为止。然后通过连接行来创建平面表示：[1] + [3, 9] + [7, 5]

Answer 3

实际上，堆排序是一种半排序算法。主要思想是每个父级都应该小于或等于其子级（最小堆排序）。 所以我们知道第一个元素是最小的。当我们弹出堆的第一个元素时，下一个最小的元素将取代它。
如需了解更多信息，请参阅以下链接：

heap sort
wikipedia