Does Python's heapify() not play well with list comprehension and slicing?

Question

I found an interesting bug in a program that I implemented somewhat lazily, and wondered if I'm comprehending it correctly. The short version is that Python's heapq implementation doesn't actually order a list, it merely groks the list in a heap-centric way. Specifically, I was expecting heapify() to result in an ordered list that facilitated list comprehension in an ordered fashion.

Using a priority cue example, as in the Python documentation:

from heapq import heapify, heappush, heappop
from random import shuffle

class Item(object):
    def __init__(self, name):
        self.name = name

lst = []

# iterate over a pseudo-random list of unique numbers
for i in sample(range(100), 15):
    it = Item("Some name for %i" % i)
    heappush(lst, (i, it))

print([i[0] for i in lst])

Results in

>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67]

This, we note, is not the original ordering of the list, but apparently some heap-centric ordering as described here. I was lazily expecting this to be fully ordered.

As a test, running the list through heapify() results in no change (as the list is already heap-ishly ordered):

heapify(lst)

print([i[0] for i in lst])

>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67]

Whereas iterating through the list with the heappop() function results in ordering as expected:

lst2 = []
while lst: lst2.append(heappop(lst))

print([i[0] for i in lst2])

>>> [2, 7, 10, 22, 27, 32, 33, 40, 45, 51, 67, 69, 89, 94, 97]

So, it would seem that heapq does not order a list (at least in the human sense of the word), but rather the heappush() and heappop() functions are able to grok the heap-ishly ordered list.

The result: Any slicing and list comprehension operations on a heapified list will yield non-ordered results.

Is this true, and is this always true?

(BTW: Python 3.0.1 on a WinXP system)

Answer 1

A heap is not a sorted list (it's a representation of a partially sorted binary tree).

So yes, you're right, if you expect a heapified list to behave like a sorted list, you'll be disappointed. The only sorting assumption you can make about a heap is that heap[0] is always its smallest element.

(It's difficult to add much to what you've already written - your question is an excellent writeup of How Things Are. 8-)

Answer 2

The result: Any slicing and list comprehension operations on a heapified list will yield non-ordered results.

Is this true, and is this always true?

If you just want to get a one-time sorted list, use:

myList.sort()

Priority queues/heaps can be used to implement a sort, or they can be used to keep a queue in priority form. Insertions into a heap are O(lg n), gets are O(1), and removals are O(lg n), which is a lot better than just resorting the entire list over and over again.

Answer 3

"""I was expecting heapify() to result in an ordered list that facilitated list comprehension in an ordered fashion.""": If this expectation was based on a reading of the manual, you should raise a docs bug report.

""" The result: Any slicing and list comprehension operations on a heapified list will yield non-ordered results. Is this true, and is this always true?""": Just like e.g. random.shuffle(), the mentioned activity is not defined to produce "ordered" results. It may produce "ordered" results occasionally, but this is coincidental and not to be relied on and not worth asking (IMHO).

Answer 4

" The result: Any slicing and list comprehension operations on a heapified list will yield non-ordered results. Is this true, and is this always true?" No, it is not always true. Although it will be non-ordered most of the time, it is possible for it to be ordered. heapify() produces a list that satisfies the "heap invariant". In this case, it is a min-heap. It turns out that a sorted list also satisfies the heap invariant (see heapq paragraph 4: "heap.sort() maintains the heap invariant"). So in theory it is possible that a heapified list will also happen to be sorted.