heapq heaps are nothing more than lists whose elements respect a special (non-unique) order.
You can use len(heap) on it just like you would on any other list.
In [1]: import heapq
In [2]: heap = [40, 10, 20, 30]
In [3]: heapq.heapify(heap)
In [4]: heap
Out[4]: [10, 30, 20, 40]
In [5]: heapq.heappop(heap)
Out[5]: 10
In [6]: heap
Out[6]: [20, 30, 40]
In [7]: len(heap)
Out[7]: 3
You should also read the python documentation for heapq: the example section should interest you.
Answer from loxaxs on Stack OverflowThe easiest way is to invert the value of the keys and use heapq. For example, turn 1000.0 into -1000.0 and 5.0 into -5.0.
You can use
import heapq
listForTree = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
heapq.heapify(listForTree) # for a min heap
heapq._heapify_max(listForTree) # for a maxheap!!
If you then want to pop elements, use:
heapq.heappop(minheap) # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap
There's no built-in in heapq to check the size, so you'll have to do that yourself:
if len(h) < capacity:
heapq.heappush(h, thing)
else:
# Equivalent to a push, then a pop, but faster
spilled_value = heapq.heappushpop(h, thing)
do_whatever_with(spilled_value)
Also, note that heapq implements a min heap, not a max heap. You'll need to reverse the order of your priorities, probably by negating them.
I found this post I was trying to implement a top-n heap with fixed size, here is the solution I can offer:
from heapq import heapify, heappush, heappushpop, nlargest
class MaxHeap():
def __init__(self, top_n):
self.h = []
self.length = top_n
heapify( self.h)
def add(self, element):
if len(self.h) < self.length:
heappush(self.h, element)
else:
heappushpop(self.h, element)
def getTop(self):
return sorted(self.h, reverse=True)
and more optimally (thanks to @CyanoKobalamyne)
from heapq import heapify, heappush, heappushpop, nlargest
class MaxHeap():
def __init__(self, top_n):
self.h = []
self.length = top_n
heapify( self.h)
def add(self, element):
if len(self.h) < self.length:
heappush(self.h, element)
else:
heappushpop(self.h, element)
def getTop(self):
return nlargest(self.length, self.h)
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]andheap[k] <= heap[2*k+2]for allk, 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.
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:
- Find-Minimum is O(1)
- Insert O(log n)
- 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