79

I tried "heapq" and arrived at the conclusion that my expectations differ from what I see on the screen. I need somebody to explain how it works and where it can be useful.

From the book Python Module of the Week under paragraph 2.2 Sorting it is written

If you need to maintain a sorted list as you add and remove values, check out heapq. By using the functions in heapq to add or remove items from a list, you can maintain the sort order of the list with low overhead.

Here is what I do and get.

import heapq
heap = []

for i in range(10):
    heap.append(i)

heap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

heapq.heapify(heap)    
heapq.heappush(heap, 10)    
heap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

heapq.heappop(heap)
0    
heap
[1, 3, 2, 7, 4, 5, 6, 10, 8, 9] <<< Why the list does not remain sorted?

heapq.heappushpop(heap, 11)
1
heap
[2, 3, 5, 7, 4, 11, 6, 10, 8, 9] <<< Why is 11 put between 4 and 6?

So, as you see the "heap" list is not sorted at all, in fact the more you add and remove the items the more cluttered it becomes. Pushed values take unexplainable positions. What is going on?

Alexander Zhukov
  • 4,357
  • 1
  • 20
  • 31
minerals
  • 6,090
  • 17
  • 62
  • 107
  • 11
    read [`heapq` the theory](http://docs.python.org/2/library/heapq.html#theory) – jfs Nov 14 '13 at 14:02
  • Start poping out data from the heap and you will understand yourself how data is sorted in a heap tree . – xor Nov 14 '13 at 14:08
  • 6
    Out of context, that quote is just wrong. A heap does not maintain a sorted list; it maintains a set of values such that the *smallest* item can be accessed in constant time, or removed in O(lg n) time. You can retrieve a sorted list by repeatedly removing the smallest item from the list. – chepner Nov 14 '13 at 14:16
  • 4
    After tracking down the quote, I see it's just plain misleading. A heap does not maintain a sorted list, but it does maintain a data structure which can be used to create a sorted list. It leaves out the detail that to retrieve the list, you must destroy the heap, which is a crucial detail. – chepner Nov 14 '13 at 14:21
  • 1
    l4mpi: I read the official python docs and still did not understand, what would be your advice?:) chepner: it is misleading, that is why I raised this question. Anyone without additional knowledge would expect `heapq` to maintain a sorted list after reading about it in the book I mentioned. – minerals Nov 14 '13 at 14:33
  • 6
    @l4mpi: No need to be *this* harsh; the quote is plainly wrong, understandably generating confusion. Algorithm theory can also be rather dry for many beginners. – Martijn Pieters Nov 14 '13 at 14:48
  • 1
    **Your book is wrong!** As you demonstrate, a heap is not a sorted list. Explanations below. – Colonel Panic Jul 03 '15 at 17:34
  • @ColonelPanic thanks! Your very generous bounty is a welcome surprise! – Martijn Pieters Jul 19 '15 at 23:55
  • If you're looking for a solution to the initial problem - that of maintaining a sorted list - have a look at the `bisect` module : https://docs.python.org/3/library/bisect.html – inegm Jun 02 '21 at 16:04

4 Answers4

112

The heapq module maintains the heap invariant, which is not the same thing as maintaining the actual list object in sorted order.

Quoting from the heapq documentation:

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

This means that it is very efficient to find the smallest element (just take heap[0]), which is great for a priority queue. After that, the next 2 values will be larger (or equal) than the 1st, and the next 4 after that are going to be larger than their 'parent' node, then the next 8 are larger, etc.

You can read more about the theory behind the datastructure in the Theory section of the documentation. You can also watch this lecture from the MIT OpenCourseWare Introduction to Algorithms course, which explains the algorithm in general terms.

A heap can be turned back into a sorted list very efficiently:

def heapsort(heap):
    return [heapq.heappop(heap) for _ in range(len(heap))]

by just popping the next element from the heap. Using sorted(heap) should be faster still, however, as the TimSort algorithm used by Python’s sort will take advantage of the partial ordering already present in a heap.

You'd use a heap if you are only interested in the smallest value, or the first n smallest values, especially if you are interested in those values on an ongoing basis; adding new items and removing the smallest is very efficient indeed, more so than resorting the list each time you added a value.

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
  • Maybe I misunderstand, but: "After that, the next 2 values will be larger (or equal) than the 1st, and the next 4 after that are going to be larger than the first 3, then the next 8 are larger, etc." – as a counter-example: `[1, 5, 9, 7, 15, 10, 11]` is a valid binary min-heap, but e.g. `7` (third level in the hierarchy) is still smaller than `9` (second level in the hierarchy). The ordered property in a heap is only true for parent–child traversal, not necessarily for "aunt–niece" relations. – Daniel Andersson Aug 23 '15 at 08:50
  • @DanielAndersson: yes, that sentence was oversimplified and through simplification, now basically wrong. Thanks for pointing that out! – Martijn Pieters Aug 23 '15 at 09:30
  • I think your usage is not that proper, heapsort(range(100, 0 , -1)), the result is like 100, 1, 2, 3 ... 98, 99. To fix it, try to heapify one time before u really pop items: ``def heapsort(heap): heapq.heapify(heap) return [heapq.heappop(heap) for _ in range(len(heap))] `` – Menglong Li Mar 02 '17 at 02:45
  • @AlbertLee: `heap` is assumed to be a proper heap. If you need to call `heapify()` first then it wasn't a proper heap; you didn't keep the heap invariant updated. – Martijn Pieters Mar 02 '17 at 07:31
  • @MartijnPieters， I think you could change ur function name like: generate_sorted_array_from_heap instead of heapysort, u agree w/ me? – Menglong Li Mar 07 '17 at 14:05
  • @AlbertLee: no, I don't. The argument name is `heap`, so the function can make that assumption. – Martijn Pieters Mar 07 '17 at 14:06
40

Your book is wrong! As you demonstrate, a heap is not a sorted list (though a sorted list is a heap). What is a heap? To quote Skiena's Algorithm Design Manual

Heaps are a simple and elegant data structure for efficiently supporting the priority queue operations insert and extract-min. They work by maintaining a partial order on the set of elements which is weaker than the sorted order (so it can be efficient to maintain) yet stronger than random order (so the minimum element can be quickly identified).

Compared to a sorted list, a heap obeys a weaker condition the heap invariant. Before defining it, first think why relaxing the condition might be useful. The answer is the weaker condition is easier to maintain. You can do less with a heap, but you can do it faster.

A heap has three operations:

  1. Find-Minimum is O(1)
  2. Insert O(log n)
  3. Remove-Min O(log n)

Crucially Insert is O(log n) which beats O(n) for a sorted list.

What is the heap invariant? "A binary tree where parents dominate their children". That is, "p ≤ c for all children c of p". Skiena illustrates with pictures and goes on to demonstrate the algorithm for inserting elements while maintaining the invariant. If you think a while, you can invent them yourself. (Hint: they are known as bubble up and bubble down)

The good news is that batteries-included Python implements everything for you, in the heapq module. It doesn't define a heap type (which I think would be easier to use), but provides them as helper functions on list.

Moral: If you write an algorithm using a sorted list but only ever inspect and remove from one end, then you can make the algorithm more efficient by using a heap.

For a problem in which a heap data structure is useful, read https://projecteuler.net/problem=500

Colonel Panic
  • 132,665
  • 89
  • 401
  • 465
  • How do you compare the efficiency of hashtable (dictionary in Python) and a heap table for doing insert/remove? I know hash table do O(1) for best case, and O(n) for worst case. Is the O(log n) for the worst or average case of a Heap?? – enaJ Jul 07 '16 at 01:21
  • @enaJ: You don’t compare them: a `dict` (or `set`) is not ordered by value at all. – Davis Herring Jan 15 '20 at 08:00
29

There is some misunderstanding of the heap data structure implementation. The heapq module is actually a variant of the binary heap implementation, where heap elements are stored in a list, as described here: https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation

Quoting Wikipedia:

Heaps are commonly implemented with an array. Any binary tree can be stored in an array, but because a binary heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, the parent and children of each node can be found by arithmetic on array indices.

This image below should help you to feel the difference between tree and list representation of the heap and (note, that this is a max heap, which is the inverse of the usual min-heap!):

enter image description here

In general, heap data structure is different from a sorted list in that it sacrifices some information about whether any particular element is bigger or smaller than any other. Heap only can tell, that this particular element is less, than it's parent and bigger, than it's children. The less information a data structure stores, the less time/memory it takes to modify it. Compare the complexity of some operations between a heap and a sorted array:

        Heap                  Sorted array
        Average  Worst case   Average   Worst case

Space   O(n)     O(n)         O(n)      O(n)

Search  O(n)     O(n)         O(log n)  O(log n)

Insert  O(1)     O(log n)     O(n)      O(n)

Delete  O(log n) O(log n)     O(n)      O(n)
Alexander Zhukov
  • 4,357
  • 1
  • 20
  • 31
1

I know this is an older question, but the OP just missed the answer, with diagrams and an explanation of why the sort order looks off when listed in a liner fashion.

(so I am not going into the optimization, efficiency, etc. I am answering the visual ordering, structure of the OP quesion)

He was at pymotw.com but if he had only gotten to: https://pymotw.com/2/heapq/

" A min-heap requires that the parent be less than or equal to its children"

So think tree, think pyramid.

This isn't a bad link at all either https://medium.com/basecs/learning-to-love-heaps-cef2b273a238

So each parent has a two-child policy. And the kids can only have two child elements as well.

The beauty of it is that the kids will always be either less than or equal to (heap-max) to their parents or more than or equal to their parents (heap min).

heap-max or heap-min (that causes confusion) refer to the top-most element or if linear,

heap[0]. Whether that represents the max value as a start or min value as a start.

I'm going to leave the math out as much as possible.

So (numbers are indices)

heap[0] has two kids. heap[1] and heap[2].

heap[1] kids would be heap[3] and heap[4]

heap[2] kids would be heap[5] and heap[6]

heap[3] kids would be heap[7] and heap[8]

heap[4] kids would be heap[9] and heap[10]

and so on.

so, the question,

[2, 3, 5, 7, 4, 11, 6, 10, 8, 9] <<< Why is 11 put between 4 and 6?

because value 11 stored at index 5. And index 5 is a child of index 2 which has the value of 3. The value 4 (index 4) and is the child of index 1

It is ordered from smallest, it just doesn't LOOK it when examined in a linear fashion.

parent -> child 

[0] -> [0] is 2
-
[0] -> [1] is 3
[0] -> [2] is 5
-
[1] -> [3] is 7
[1] -> [4] is 4
[2] -> [5] is 11  <-- between 4 and 6
[2] -> [6] is 6

so.... this again. And it is true. "A min-heap requires that the parent be less than or equal to its children"

Make yourself crazy and pencil it out for max.... it will be true still.

(ever write one of these things and just wait to get squashed by some post doctoral?)

so let's pop off the first element and do like a normal list or queue

[0] -> [0] is 3
-
[0] -> [1] is 5
[0] -> [2] is 7
-
[1] -> [3] is 4
[1] -> [4] is 11

Let's stop.

index 1 has a value of 5. index 3, it child's value is 4 and is smaller.... the rule is broken. The heap is reordered to maintain the relationships. so it will basically, never look sorted and it won't look anything like the prior iteration of itself before popping off the value.

There are ways to reorder the node, and that second article talks bout them. I just wanted to answer the question specifically.

IGotAHeadache
  • 33
  • 5