Algorithms For Dummies

  Reconnecting the Dots 

     187

This example uses a class that allows it to perform priority-queue comparisons 

that determine whether the queue contains elements and when those elements 

contain a certain edge (avoiding double insertions). The priority queue has another 

useful characteristic (whose usefulness is explained when working on Dijkstra’s 

algorithm): If you insert an edge with a different weight than previously stored, 

the code updates the edge weight and rearranges the edge position in the heap.

from heapq import heapify, heappop, heappush

class priority_queue():

    def __init__(self):

        self.queue = list()

        heapify(self.queue)

        self.index = dict()

    def push(self, priority, label):

        if label in self.index:

            self.queue = [(w,l)

                for w,l in self.queue if l!=label]

            heapify(self.queue)

        heappush(self.queue, (priority, label))

        self.index[label] = priority

    def pop(self):

        if self.queue:

            return heappop(self.queue)

    def __contains__(self, label):

        return label in self.index

    def __len__(self):

        return len(self.queue)