class PriorityQueue:
    """
    Implements a heap-style priority queue with O(lg n) enqueue and
    dequeue methods.  The priority queue is stored as a list where
    position 0 always contains None.  The first actual item is stored
    in position 1.  This is necessary so that the list can be treated
    as a binary tree and simple calculations can be done to find the
    parent, and left and right sub-trees. The items being stored are
    expected to be instances of a class which has a priority() method.
    """
    def __init__(self):
        self.q = [None]
    def __str__(self):
        result = "Queue contains " + str(len(self.q)-1) + " items"
        if not self.empty():
            result += "-Minimum item has priority: " + \
                      str(self.min().priority())
        return result
    def parent(self, i):
        return i/2
    def right(self, i):
        return (i * 2) + 1
    def left(self, i):
        return i * 2
    def hasLeft(self, i):
        return self.left(i) <= len(self.q)-1
    def hasRight(self, i):
        return self.right(i) <= len(self.q)-1
    def empty(self):
        return len(self.q) == 1
    def swap(self, p1, p2):
        self.q[p1], self.q[p2], = self.q[p2], self.q[p1]
    def bubbleUp(self,i):
        p = self.parent(i)
        if i==1 or self.q[i].priority() >= self.q[p].priority():
            return
        else:
            self.swap(i, p)
            self.bubbleUp(p)
    def bubbleDown(self, i):
        if (not self.hasLeft(i)) and (not self.hasRight(i)):
            return
        elif self.hasLeft(i) and (not self.hasRight(i)):
            l = self.left(i)
            if self.q[i].priority() > self.q[l].priority():
                self.swap(i, l)
                self.bubbleDown(l)
        else:
            l = self.left(i)
            r = self.right(i)
            key = self.q[i].priority()
            if self.q[l].priority() >= key and self.q[r].priority() >= key:
                return
            elif self.q[l].priority() <= self.q[r].priority():
                self.swap(i, l)
                self.bubbleDown(l)
            else:
                self.swap(i, r)
                self.bubbleDown(r)
    def min(self):
        if self.empty():
            raise RunTimeError
        return self.q[1]
    def dequeue(self):
        if self.empty():
            raise RunTimeError
        result = self.q.pop(1)
        self.q.insert(1, self.q.pop(len(self.q)-1))
        self.bubbleDown(1)
        return result
    def enqueue(self, item):
        self.q.append(item)
        self.bubbleUp(len(self.q)-1)

if __name__ == '__main__':
    class Test:
        """
        A simple class created to test the priority queue.
        The PriorityQueue class expects to store instances
        of a class that has a method called priority().
        """
        def __init__(self, v):
            self.value = v
        def __str__(self):
            return str(self.value)
        def priority(self):
            return self.value

    print "Creating a PriorityQueue"
    pq = PriorityQueue()
    print "Check that an empty queue is printable"
    print pq
    print "Inserting 10, 5, 2, 12, 25"
    pq.enqueue(Test(10))
    pq.enqueue(Test(5))
    pq.enqueue(Test(2))
    pq.enqueue(Test(12))
    pq.enqueue(Test(25))
    print pq
    print "Removing the minimum until empty"
    while (not pq.empty()):
        print pq.dequeue()