Priority queue (with delete by label)

A simple priority queue implementation with O(n log n) sorting. The underlying data structure is a binary heap.

This implementation uses a binary heap where each node is less than or equal to its children. Nodes can be anything as long as they’re comparable.

Like all priority queues, this implementation efficiently retrieves the minimum element (by comparative value) in the queue. You can also insert elements and delete elements if they are “labeled”. (See examples below.)

Usage

from heap import PriorityQueue

q = PriorityQueue([3, 1, 2, 4])

assert q.min == 1                 # get  minimum element
assert q.sort() == [1, 2, 3, 4]   # get sorted list of elements

x = q.shift()                     # shift off minimum element
assert x == 1
assert q.sort() == [2, 3, 4]

Alternatively, you can populate your priority queue with Node instances:

a = Node(label='a', priority=1)

Nodes are just python dicts comparable by their priority key.

from heap import Node, PriorityQueue

a = Node(label='a', msg="boom!", priority=1)
b = Node(label='b', msg="hi", priority=2)
c = Node(label='c', msg="ok", priority=3)
d = Node(label='d', msg="oh", priority=4)

assert a < b < c < d

If you initialize your queue with Node objects containing node.label attributes, you can then delete nodes by label:

q = PriorityQueue([b, c, d])

assert q.min == b
assert q.min.msg == 'hi'
assert q.min.label == 'b'
assert q == [b, c, d]

q.insert(a)
assert q.min == a
assert q.min.msg is 'boom!'
assert q.min.label is 'a'
assert q.sort() == [a, b, c, d]   # get sorted list of elements

min = q.shift()                   # shift off minimum element
assert min == a
assert min.label == 'a'
assert q.sort() == [b, c, d]

assert q.delete('c') == c         # delete a node by `node.label`
assert q.sort() == [b, d]
assert q.min == b

See Also

• priority queues with binary heaps - nice tutorial and walkthrough of a python implementation

• pqdict - an indexed priority queue with a dictionary interface