Welcome, guest | Sign In | My Account | Store | Cart

Notice! PyPM is being replaced with the ActiveState Platform, which enhances PyPM’s build and deploy capabilities. Create your free Platform account to download ActivePython or customize Python with the packages you require and get automatic updates.

pypm install pqdict

How to install pqdict

  1. Download and install ActivePython
  2. Open Command Prompt
  3. Type pypm install pqdict
 Python 2.7Python 3.2Python 3.3
Windows (32-bit)
Windows (64-bit)
Mac OS X (10.5+)
Linux (32-bit)
Linux (64-bit)
0.3 Available View build log
Lastest release
version 0.3 on Sep 20th, 2013

Implementation of an indexed priority queue written in pure Python. The PQDict class provides the MutableMapping protocol and its instances operate like regular Python dictionaries with a couple extra methods. Think of a Priority Queue Dictionary as a mapping of "dictionary keys" to "priority keys".

What is an "indexed" priority queue?

A priority queue is an abstract data structure that allows you to serve elements in a prioritized fashion. You can insert elements with priorities, and remove or peek at the top priority element. Unlike a standard priority queue, an indexed priority queue additionally allows you to alter the priority of any element in the queue. With the right implementation, each of these operations can be done quite efficiently.

How does it work?

The priority queue is implemented as a binary heap (using a python list), 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 elements to their position in the heap. This index is synchronized with the heap as the heap is manipulated. As a result, PQDict 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

Why would I want something like that?

Indexed priority queues can be very useful as schedulers for applications like simulations. They can also be used in efficient implementations of Dijkstra's shortest-path algorithm. Basically, whenever we not only want to be able to quickly find the minimum or maximum element, but we also need to be able to dynamically find and modify the priorities of existing elements in the queue efficiently.


By default, PQDict uses a min-heap, meaning smaller priority keys have higher priority. Use PQDict.maxpq() to create a max-heap priority queue.

System Message: ERROR/3 (<string>, line 62)

Unknown directive type "code".

.. code:: python

    from pqdict import PQDict

    # same input signature as dict()
    pq = PQDict(a=3, b=5, c=8)
    pq = PQDict(zip(['a','b','c'], [3, 5, 8]))
    pq = PQDict({'a':3, 'b':5, 'c':8})

    # add/update items this way...
    pq.additem('d', 15)
    pq.updateitem('c', 1)

    # ...or this way
    pq['d'] = 6.5
    pq['e'] = 2
    pq['f'] = -5

    # get an element's priority
    pkey = pq['f']
    print pkey          # -5
    print 'f' in pq     # True

    # remove an element and get its priority key
    pkey = pq.pop('f')
    print pkey          # -5
    print 'f' in pq     # False

    pkey = pq.get('f', None)
    print pkey          # None

    # or just delete an element
    del pq['e']

    # peek at the top priority item
    print pq.peek()     # ('c', 1)

    # let's do a manual heapsort
    print pq.popitem()  # ('c', 1)
    print pq.popitem()  # ('a', 3)
    print pq.popitem()  # ('b', 5)
    print pq.popitem()  # ('d', 6.5)

    # and we're empty!
    pq.popitem()        # KeyError

Regular iteration has no prescribed order and is non-destructive.

System Message: ERROR/3 (<string>, line 110)

Unknown directive type "code".

.. code:: python

    queue = PQDict({'Alice':1, 'Bob':2})
    for customer in queue:
        serve(customer) # Bob may be served before Alice!

This also applies to pq.keys(), pq.values(), pq.items() and using iter().

System Message: ERROR/3 (<string>, line 118)

Unknown directive type "code".

.. code:: python

    >>> PQDict({'a': 1, 'b': 2, 'c': 3, 'd': 4}).keys()
    ['a', 'c', 'b', 'd']

Destructive iteration methods return generators that pop items out of the heap, which amounts to performing a heapsort:

System Message: ERROR/3 (<string>, line 125)

Unknown directive type "code".

.. code:: python

    for customer in queue.iterkeys():
        serve(customer) # Customer satisfaction guaranteed :)
    # queue is now empty

The destructive iterators are pq.iterkeys(), pq.itervalues(), and pq.iteritems().

There is also a convenience function to sort a dictionary-like object by value using a PQDict. It is non-destructive and returns a sorted list of dictionary items.

System Message: ERROR/3 (<string>, line 135)

Unknown directive type "code".

.. code:: python

    from pqdict import heapsorted_by_value

    billionaires = {'Bill Gates': 72.7, 'Warren Buffett': 60.0, ...}
    top10_richest = heapsorted_by_value(billionaires, maxheap=True)[:10]


This module was written by Nezar Abdennur and is released under the MIT license. It makes use of some code that was adapted from the Python implementation of the heapq module, which was written by Kevin O'Connor and augmented by Tim Peters and Raymond Hettinger.

Subscribe to package updates

Last updated Sep 20th, 2013

Download Stats

Last month:1

What does the lock icon mean?

Builds marked with a lock icon are only available via PyPM to users with a current ActivePython Business Edition subscription.

Need custom builds or support?

ActivePython Enterprise Edition guarantees priority access to technical support, indemnification, expert consulting and quality-assured language builds.

Plan on re-distributing ActivePython?

Get re-distribution rights and eliminate legal risks with ActivePython OEM Edition.