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.

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.

Most viewed recipes tagged "priority_queue"

Priority queue dictionary (Python)

Priority Queue (with deletion) (Python)