Python内置堆(heapq)：如果反转(最大堆)，会出现奇怪的行为

Question

我想使用Python (2.0)内置的min-heap数据结构，来自heapq模块(https://docs.python.org/3/library/heapq.html)，以构建一个max-heap。为此，我只需使用我需要推入堆中的数字的负数即可。

使用这个(max-heap版本):

import heapq
h=[]
for i in xrange(10):
    heapq.heappush(h,-i)
    print h

我得到了一些看起来不正确的东西：

[0]
[-1, 0]
[-2, 0, -1]
[-3, -2, -1, 0]
[-4, -3, -1, 0, -2]
[-5, -3, -4, 0, -2, -1]
[-6, -3, -5, 0, -2, -1, -4]
[-7, -6, -5, -3, -2, -1, -4, 0]
[-8, -7, -5, -6, -2, -1, -4, 0, -3]
[-9, -8, -5, -6, -7, -1, -4, 0, -3, -2]

最小堆版本看起来不错:

import heapq
h=[]
for i in xrange(10):
    heapq.heappush(h,i)
    print h

正如你所见：

[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
[0, 1, 2, 3, 4]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

我错过了什么？

我查看了其他SE的问题/答案（例如，python topN max heap, use heapq or self implement?，What do I use for a max-heap implementation in Python?等），但它们没有提到这个问题。

- SergeGardien

---

你在两个例子中都发布了相同的代码... - Jon Clements

这是一个堆，而不是排序列表。一切都好。 - user2357112

Answer 1

正如@user2357112所提到的，这是一个小根堆。输出结果没有问题。两个输入的区别在于，第一种情况下你按排序方式输入数据，在第二种情况下，你按相反顺序输入数据。

小根堆的特性是：每个节点的值都大于或等于它的父节点值，并且最小值元素位于根节点。

案例1：逆序输入= 10,9,8,7,6

         10
        [10]

         9
        /
      10
      [9,10]


        8
       / \
     10   9
     [8,10,9]


        7
       / \
      8   9
     /
    10
    [7, 8,9,10]

        6
       / \
      7   9
     / \
    10  8
    [6,7,9,10,8]

案例2：已排序的输入 = 1、2、3、4、5

         1
        [1]

         1
        /
       2
      [1,2]


        1
       / \
      2   3
     [1,2,3]


        1
       / \
      2   3
     /
    4
    [1,2,3,4]

        1
       / \
      2   3
     / \
    4   5
    [1,2,3,4,5]

如果您想了解堆是如何构建的，以及在每个输入之后如何保持平衡，请访问以下网址。您可以逐个插入元素并查看其效果。 https://www.cs.usfca.edu/~galles/JavascriptVisual/Heap.html

- Renuka Deshmukh

---

非常感谢你的回答，Renuka。你的树状图可视化特别有用，包括提到的带交互式可视化的链接。这个网站https://www.cs.usfca.edu/~galles/JavascriptVisual/Algorithms.html提供了各种数据结构，实际上做得非常好。 - SergeGardien

Answer 2

一个最小堆的不变量是每个节点都比它的子节点小；两个子节点之间没有暗示的顺序（因此，给定一组值，可能存在许多有效的排序方式；唯一具有绝对固定位置的值是树的根部的最小值）。请注意，这也适用于您的输出：

                  ,------------------,
  ,---+---,   ,---|----------+---,   |
  |   V   V   |   |          V   V   V
[-9, -8, -5, -6, -7, -1, -4, 0, -3, -2]
      |   |   ^   ^   ^   ^
      `---|---+---'   |   |
          `-----------+---'

你的另一个例子最终以完全排序的顺序结束，只是一种巧合，这取决于项目插入堆中的不同顺序。

- jasonharper