Python 内置堆 (heapq)：倒置时的奇怪行为（最大堆）

Question

我正在尝试使用 heapq 模块 (https://docs.python.org/3/library/heapq.html) 中的 Python (2.0) 内置最小堆数据结构来构建最大堆。为此，我只需使用我需要推入堆中的数字的负数。

使用这个（最大堆版本）：

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 questions/answers（例如 python topN max heap, use heapq or self implement?, What do I use for a max-heap implementation in Python? 等），但他们没有提到这个问题。

Answer 1

一个min-heap的不变量是每个节点都小于它的任何一个children；两个 children 之间没有隐含的顺序（因此，一组给定的值可以有许多有效的顺序；唯一具有绝对固定位置的值是最小值，在树的根部).请注意，您的输出也是如此：

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

事实上，您的另一个示例以完全排序的顺序结束，这只是一个巧合，因为项目插入堆的顺序不同。

Answer 2

正如@user2357112 已经提到的，它是一个最小堆。输出没有问题。两种输入之间的区别在于，在第一种情况下，您以排序的方式输入数据，而在第二种情况下，您以反向排序的方式输入数据。

the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.

案例 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]

如果您对堆的构建方式以及每次输入后堆的平衡方式感兴趣，请转到以下内容url。您可以一次插入一个元素并查看它的运行情况。 https://www.cs.usfca.edu/~galles/JavascriptVisual/Heap.html

Python 内置堆 (heapq)：倒置时的奇怪行为（最大堆）

Python built-in heap (heapq): Odd behavior if inverted (max-heap)

python

heap

min-heap

max-heap