python中的堆顺序

Question

新的堆数据结构。

试图从列表中创建堆。

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

heapq.heapify(li)

在堆后，输出是

[1, 3, 9, 7, 5]

为什么要下这个命令？

我认为对于一个最小优先级堆，元素应该从min排序到max，即

heapq.heapify(li)应该与li.sort()相同

有人能帮我理解吗？

Answer 1

堆实际上不是按照列表排序的方式排序的。Python没有唯一的堆数据结构，并且使用带有堆操作的列表，这可能是造成一些人困惑的原因。排序(最小优先级)堆是满足“堆条件”的堆，因此任何子节点都大于其父节点。这并不意味着扁平的表示将是有序的。

在扁平之前，您的示例将如下所示：

    1
   / \
  3   9
 / \
7   5

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

Answer 2

将堆看作一棵树比较容易：

         1
     3      9
  7     5

其中每个节点小于其两个子节点，但子节点的顺序无关(这将堆与二进制搜索树区分开来)。

一棵完整的树允许在数组中嵌入一个简单的嵌入，方法是按宽度一阶对节点编号，从根作为节点1开始。

         1(1)
     3(2)      9(3)
  7(4)     5(5)

在这种情况下，下列关系成立：

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 3

实际上，堆排序是一种半排列的算法。主要思想是，每个父级都应该小于或等于其子级(在最小堆排序中)。所以我们知道第一个元素是最小的。当我们弹出堆的第一个元素时，下一个最小的元素将取代它。

有关更多信息，请参见这些liks：

堆排序

维基百科