Does Python's heapify() not play well with list comprehension and slicing?
heap, list-comprehension, python
Solution
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-)
Problem
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)