Popular Python recipes tagged "heapq"

Priority Queue (with deletion) (Python)

2013-12-08T21:12:55-08:00

Python recipe 578780 by elazar (artificial_intelligence, heap, heapq, priority_queue, queue). Revision 5.

Based on the interface defined in aima-python http://aima-python.googlecode.com/svn/trunk/utils.py

Yields better performance.

Priority queue dictionary (Python)

2013-08-25T00:23:12-07:00

Python recipe 578643 by Nezar Abdennur (algorithms, dictionary, heap, heapq, pqdict, priority_queue). Revision 4.

An indexed priority queue implemented in pure python as a dict-like class. It is a stripped-down version of pqdict. A Priority Queue Dictionary maps dictionary keys (dkeys) to updatable priority keys (pkeys).

The priority queue is implemented as a binary heap, which supports:

O(1) access to the top priority element
O(log n) removal of the top priority element
O(log n) insertion of a new element

In addition, an internal dictionary or "index" maps dictionary keys to the position of their entry in the heap. This index is maintained as the heap is manipulated. As a result, a PQ-dict also supports:

O(1) lookup of an arbitrary element's priority key
O(log n) removal of an arbitrary element
O(log n) updating of an arbitrary element's priority key

A data structure like this can be used to drive simulations, schedulers, certain greedy algorithms, merging streams of sorted data, and other applications where priorities may need to be changed frequently.

asyncore scheduler (Python)

2011-07-25T23:42:21-07:00

Python recipe 577808 by Giampaolo Rodolà (asynchronous, asyncore, heapq, nonblocking, scheduler, twisted). Revision 5.

The thing I miss mostly in asyncore is a system for calling a function after a certain amount of time without blocking. This is crucial for simple tasks such as disconnecting a peer after a certain time of inactivity or more advanced use cases such as bandwidth throttling.

This recipe was initially inspired by Twisted's internet.base.DelayedCall class:

http://twistedmatrix.com/trac/browser/tags/last_vfs_and_web2/twisted/internet/base.py#L34

...then included into pyftpdlib:

http://code.google.com/p/pyftpdlib/issues/detail?id=72

...and finally proposed for inclusion into asyncore:

http://bugs.python.org/issue1641

Handling ties for top largest/smallest elements (Python)

2009-04-07T18:57:35-07:00

Python recipe 576712 by George Sakkis (heapq, largest, smallest, top). Revision 8.

The heapq module provides efficient functions for getting the top-N smallest and largest elements of an iterable. A caveat of these functions is that if there are ties (i.e. equal elements with respect to the comparison key), some elements may end up in the returned top-N list while some equal others may not:

>>> nsmallest(3, [4,3,-2,-3,2], key=abs)
[-2, 2, 3]

Although 3 and -3 are equal with respect to the key function, only one of them is chosen to be returned. For several applications, an all-or-nothing approach with respect to ties is preferable or even required.

A new optional boolean parameter 'ties' is proposed to accomodate these cases. If ties=True and the iterable contains more than N elements, the length of the returned sorted list can be lower than N if not all ties at the last position can fit in the list:

>>> nsmallest(3, [4,3,-2,-3,2], key=abs, ties=True)
[-2, 2]