API Reference

pqdict class

class pqdict.pqdict(data=None, key=None, reverse=False, precedes=<built-in function lt>)[source]

A collection that maps hashable objects (keys) to priority-determining values. The mapping is mutable so items may be added, removed and have their priority level updated.

Parameters:

data : mapping or iterable, optional

Input data, e.g. a dictionary or a sequence of items.

key : callable, optional

Optional priority key function to transform values into priority keys for sorting. By default, the values are not transformed.

reverse : bool, optional

If True, larger priority keys give items higher priority. Default is False.

precedes : callable, optional (overrides reverse)

Function that determines precedence of a pair of priority keys. The default comparator is operator.lt, meaning smaller priority keys give items higher priority.

Attributes

Methods

classmethod fromkeys(iterable, value, **kwargs)[source]

Return a new pqict mapping keys from an iterable to the same value.

heapify([key])[source]

Repair a broken heap. If the state of an item’s priority value changes you can re-sort the relevant item only by providing key.


Properties

keyfn

Priority key function

precedes

Priority key precedence function


Dictionary API

These do as expected. See dict for more details.

len(pq)
pq[key]
pq[key] = value
del pq[key]
key in pq
get(key[, default])

D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.

pop([key[, default]])[source]

If key is in the pqdict, remove it and return its priority value, else return default. If default is not provided and key is not in the pqdict, raise a KeyError.

clear() → None. Remove all items from D.
update([other])

D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. If E present and has a .keys() method, does: for k in E: D[k] = E[k] If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v In either case, this is followed by: for k, v in F.items(): D[k] = v

setdefault(key[, default])

D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D

copy()[source]

Return a shallow copy of a pqdict.

Iterators and Views

Warning

For the following sequences, order is arbitrary.

iter(pq)
keys() → a set-like object providing a view on D's keys
values() → an object providing a view on D's values
items() → a set-like object providing a view on D's items

Note

In Python 2, the above methods return lists rather than views and pqdict includes additional iterator methods iterkeys(), itervalues() and iteritems().


Priority Queue API

top()[source]

Return the key of the item with highest priority. Raises KeyError if pqdict is empty.

pop([key[, default]])[source]

If key is not provided, remove the top item and return its key, or raise KeyError if the pqdict is empty.

additem(key, value)[source]

Add a new item. Raises KeyError if key is already in the pqdict.

updateitem(key, new_val)[source]

Update the priority value of an existing item. Raises KeyError if key is not in the pqdict.

topitem()[source]

Return the item with highest priority. Raises KeyError if pqdict is empty.

popitem()[source]

Remove and return the item with highest priority. Raises KeyError if pqdict is empty.

pushpopitem(key, value)[source]

Equivalent to inserting a new item followed by removing the top priority item, but faster. Raises KeyError if the new key is already in the pqdict.

replace_key(key, new_key)[source]

Replace the key of an existing heap node in place. Raises KeyError if the key to replace does not exist or if the new key is already in the pqdict.

swap_priority(key1, key2)[source]

Fast way to swap the priority level of two items in the pqdict. Raises KeyError if either key does not exist.

Heapsort Iterators

Note

Iteration is in descending order of priority.

Danger

Heapsort iterators are destructive: they are generators that pop items out of the heap, which amounts to performing a heapsort.

popkeys()[source]

Heapsort iterator over keys in descending order of priority level.

popvalues()[source]

Heapsort iterator over values in descending order of priority level.

popitems()[source]

Heapsort iterator over items in descending order of priority level.

Warning

The names of the heapsort iterators in v0.5 (iterkeys, itervalues, iteritems) were changed in v0.6 to be more transparent: These names are not provided at all in Python 3, and in Python 2 they are now part of the dictionary API.

Functions

pqdict.nsmallest(n, mapping)[source]

Takes a mapping and returns the n keys associated with the smallest values in ascending order. If the mapping has fewer than n items, all its keys are returned.

Equivalent to:
next(zip(*heapq.nsmallest(mapping.items(), key=lambda x: x[1])))
Returns:list of up to n keys from the mapping
pqdict.nlargest(n, mapping)[source]

Takes a mapping and returns the n keys associated with the largest values in descending order. If the mapping has fewer than n items, all its keys are returned.

Equivalent to:
next(zip(*heapq.nlargest(mapping.items(), key=lambda x: x[1])))
Returns:list of up to n keys from the mapping