priorityq 0.0.8

Features

• O(1) finding of elements

• Deletion of elements possible (in O(log n)).

• Adjusting of the priority of an element without requiring a deletion followed by an insertion.

• Opaque handles to elements that can be used to reference to the same item again.

• Duplicate elements allowed.

• Custom comparator function can be passed to the PQ itself instead of needing to implement __cmp__.

It is simple to use

To create a PQ simply do:

# A simple object with a comparator
class Item(object):
    def __init__(self, value):
        self.value = value
    def __cmp__(self, another):
        return cmp(self.value, another.value)

from priorityq import PQ
pq = PQ()
pq.heapify([Item(r) for r in [1, 10, 2, 20, 4, 7, 9, 3, 5, 6]])

print list(pq)

# Should print:
# 1 2 3 4 5 6 7 9 10 20

handle_10 = pq.find(10)   #   Happens in O(1)

handle_10.value = 25      #   Modify its value - O(log n)
pq.adjust(handle_10)      #   Indicate to the heap to reprioritise/adjust it

print list(pq)

# Should print:
# 1 2 3 4 5 6 7 9 20 25

handle_10.value = 10      #   Modify its value using the same opaque handle as before
pq.adjust(handle_10)      #   Indicate to the heap to reprioritise/adjust it

print list(pq)

# Should print:
# 1 2 3 4 5 6 7 9 10 20

Links

• Documentation Wiki

• Website