Python built-in heap (heapq): Odd behavior if inverted (max-heap)
I'm trying to use Python's (2.0) built-in mini-heap data structure from the heapq module ( https://docs.python.org/3/library/heapq.html ) to build the maximum heap. To do this, I just use negative numbers that I need to insert into my heap.
Using this (max-heap version):
import heapq
h=[]
for i in xrange(10):
heapq.heappush(h,-i)
print h
I am getting what doesn't look right:
[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]
Instead, the mini heap 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 checked the other questions / answers SE (eg, for python TopN max heap, use the self heapq or sell? , What do I use to implement max-heap in Python? Etc.), but they do not mention this problem.
source to share
As @ user2357112 mentioned this is a mini heap. There is nothing wrong with getting out. The difference between the two inputs is that in the first scenario you enter data in a sorted manner, and in the second scenario you enter data in the sorted order in reverse order.
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 each input, go to the next url. You can insert one element at a time and see it in action. https://www.cs.usfca.edu/~galles/JavascriptVisual/Heap.html
source to share
The mini-heap invariant is that each node is smaller than any of its children; there is no implied ordering between the two children (and therefore there can be many valid orders of a given set of values, the only value that has an absolutely fixed position is the minimum at the root of the tree). Note that this is true for 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 a fully sorted order is just a coincidence based on the different order in which the elements were inserted into the heap.
source to share