1 1 2:mod:`heapq` --- Heap queue algorithm ===================================== .. module:: heapq :synopsis: Heap queue algorithm (a.k.a. priority queue). .. moduleauthor:: Kevin O'Connor .. sectionauthor:: Guido van Rossum .. sectionauthor:: François Pinard .. sectionauthor:: Raymond Hettinger .. versionadded:: 2.3 **Source code:** :source:`Lib/heapq.py` -------------- This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. 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]``. 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 :func:`heapify`. The following functions are provided: .. function:: heappush(heap, item) Push the value *item* onto the *heap*, maintaining the heap invariant. .. function:: heappop(heap) Pop and return the smallest item from the *heap*, maintaining the heap invariant. If the heap is empty, :exc:`IndexError` is raised. .. function:: heappushpop(heap, item) Push *item* on the heap, then pop and return the smallest item from the *heap*. The combined action runs more efficiently than :func:`heappush` followed by a separate call to :func:`heappop`. .. versionadded:: 2.6 .. function:: heapify(x) Transform list *x* into a heap, in-place, in linear time. .. function:: heapreplace(heap, item) 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, :exc:`IndexError` is raised. This one step operation is more efficient than a :func:`heappop` followed by :func:`heappush` and can be more appropriate when using a fixed-size heap. The pop/push combination always returns an element from the heap and replaces it with *item*. The value returned may be larger than the *item* added. If that isn't desired, consider using :func:`heappushpop` instead. Its push/pop combination returns the smaller of the two values, leaving the larger value on the heap. The module also offers three general purpose functions based on heaps. .. function:: merge(*iterables) Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns an :term:`iterator` over the sorted values. Similar to ``sorted(itertools.chain(*iterables))`` but returns an iterable, does not pull the data into memory all at once, and assumes that each of the input streams is already sorted (smallest to largest). .. versionadded:: 2.6 .. function:: nlargest(n, iterable[, key]) Return a list with the *n* largest elements from the dataset defined by *iterable*. *key*, if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: ``key=str.lower`` Equivalent to: ``sorted(iterable, key=key, reverse=True)[:n]`` .. versionadded:: 2.4 .. versionchanged:: 2.5 Added the optional *key* ar