|
New in version 2.3.
This module provides an implementation of the heap queue algorithm, also known as the
priority queue algorithm.
Heaps are 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 heap[0]
is always its smallest element.
The API below differs from textbook heap algorithms in two aspects: (a) We use zero-based
indexing. This makes the relationship between the index for a node and the indexes for its
children slightly less obvious, but is more suitable since Python uses zero-based indexing.
(b) Our pop method returns the smallest item, not the largest (called a "min heap"
in textbooks; a "max heap" is more common in texts because of its suitability for
in-place sorting).
These two make it possible to view the heap as a regular Python list without surprises: heap[0]
is the smallest item, and heap.sort() maintains the heap invariant!
To create a heap, use a list initialized to [], or you can transform a
populated list into a heap via function heapify().
The following functions are provided:
-
- Push the value item onto the heap, maintaining the heap invariant.
-
- Pop and return the smallest item from the heap, maintaining the heap
invariant. If the heap is empty, IndexError is raised.
-
- Transform list x into a heap, in-place, in linear time.
-
- Pop and return the smallest item from the heap, and also push the new item.
The heap size doesn't change. If the heap is empty, IndexError
is raised. This is more efficient than heappop() followed by heappush(), and can be more appropriate when using a fixed-size
heap. Note that the value returned may be larger than item! That constrains
reasonable uses of this routine.
Example of use:
>>> from heapq import heappush, heappop
>>> heap = []
>>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
>>> for item in data:
... heappush(heap, item)
...
>>> sorted = []
>>> while heap:
... sorted.append(heappop(heap))
...
>>> print sorted
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> data.sort()
>>> print data == sorted
True
>>>
|
