CODEWITHSUNDEEP
pythonpython-2.7heap
Kevin
Kevin

Reputation: 1085

How does python order values in a heap?

For example, a list of random numbers:

>>> x = [1,24,5,1,5,1,23,6]
>>> heapq.heapify(x)
[1, 1, 1, 6, 5, 5, 23, 24]

Why does it arbitrarily do 6,5,5 and not 5,5,6 or 5,6,5?

Upvotes: 0

Views: 48

Answers (1)

niemmi
niemmi

Reputation: 17263

Python docs contain following description of heapq:

Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This implementation uses arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that its smallest element is always the root, heap[0].

You can verify this with your example data:

>>> for i in xrange(len(x)):
...     print '{0} <= {1}'.format(x[i], x[i*2+1:i*2+3])
...
1 <= [1, 1]
1 <= [6, 5]
1 <= [5, 23]
6 <= [24]
5 <= []
5 <= []
23 <= []
24 <= []

For more information about binary heaps you can check Wikipedia.

Upvotes: 3

Related Questions