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

Question

I'm trying to use the Python (2.0) built-in min-heap data structure from the heapq module (https://docs.python.org/3/library/heapq.html) to build a max-heap. To do that I simply use the negative of the numbers I need to push into my heap.

Using this (max-heap version):

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

I get something which doesn't look correct:

[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]

The min-heap version instead looks fine:

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

As you can see:

[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]

What am I missing?

I've checked other SE questions/answers (e.g., python topN max heap, use heapq or self implement?, What do I use for a max-heap implementation in Python?, etc.) but they don't mention this issue.

You've posted the same code for both examples... – Jon Clements Aug 02 '17 at 17:20 — Jon Clements, Aug 02 '17 at 17:20
It's a heap, not a sorted list. Everything is fine. – user2357112 Aug 02 '17 at 17:22 — user2357112, Aug 02 '17 at 17:22

Renuka Deshmukh · Accepted Answer · 2017-08-02T18:08:52.613

As @user2357112 already mentioned, it is a min-heap. There is nothing wrong with the output. The difference between the 2 inputs is that, in the first scenario you enter the data in sorted fashion and in the second scenario, you input the data in reverse sorted fashion.

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.

Case 1 : Reverse Sorted Input = 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]

Case 2 : Sorted Input = 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]

If you are interested in how the heap is built and how it balances after every input, go to the following url. You can insert one element at a time and see it in action. https://www.cs.usfca.edu/~galles/JavascriptVisual/Heap.html

Many thanks for your answer Renuka. Your tree-graph visualization has been particularly useful, included the mentioned link with the interactive visualization. The website [https://www.cs.usfca.edu/~galles/JavascriptVisual/Algorithms.html](https://www.cs.usfca.edu/~galles/JavascriptVisual/Algorithms.html) for various data structures is actually very well made. — SergeGardien, Aug 02 '17 at 19:36

jasonharper · Answer 2 · 2017-08-02T17:53:19.040

The invariant of a min-heap is that each node is less than either of its children; there is no implied ordering between the two children (and therefore, there can be many valid orderings of a given set of values; the only value that has an absolutely fixed position is the minimum one, at the root of the tree). Note that this is true of your output:

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

The fact that your other example ended up in completely sorted order is merely a coincidence, based on the different order in which items were inserted into the heap.

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

2 Answers2