Priority Queue
  1. #!/usr/bin/python
  2. """ A modeule containing Priority Queue class and corresponding functions"""
  3.  
  4. def getList():
  5.     return [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
  6.  
  7. def getRandomList():
  8.     import random
  9.  
  10.     random.seed()
  11.  
  12.     l = []
  13.     for i in range(10):
  14.         l.append(random.choice(range(10)))
  15.  
  16.     return l
  17.  
  18. class PriorityQueue(object):
  19.     def __init__(self, l):
  20.         self._l = l
  21.         self.buildMaxHeap()
  22.  
  23.     @property
  24.     def l(self):
  25.         return self._l
  26.  
  27.     @l.setter
  28.     def l(self, l):
  29.         self._l = l
  30.  
  31.     @l.deleter
  32.     def l(self):
  33.         del self._l
  34.  
  35.     def getLeft(self, index):
  36.         """Get the index of left child
  37.  
  38.         Args:
  39.             index (int), index of current node
  40.  
  41.         Returns:
  42.             int, index of the left child
  43.         """
  44.         return index*2+1
  45.  
  46.     def getRight(self, index):
  47.         """Get the index of right child
  48.  
  49.         Args:
  50.             index (int), index of current node
  51.  
  52.         Returns:
  53.             int, index of the right child
  54.         """
  55.         return index*2+2
  56.  
  57.     def getParent(self, index):
  58.         return int((index-1)/2)
  59.  
  60.     def maxHeapify(self, index, n):
  61.         """Max heapify the tree
  62.  
  63.         Args:
  64.             i (int), index of current node
  65.             n (int), index of the last node
  66.         """
  67.         left = self.getLeft(index)
  68.         right = self.getRight(index)
  69.  
  70.         largest = index
  71.         if left <= n and self._l[left] > self._l[index]:
  72.             largest = left
  73.  
  74.         if right <= n and self._l[right] > self._l[largest]:
  75.             largest = right
  76.  
  77.         if largest != index:
  78.             self._l[largest], self._l[index] = self._l[index], self._l[largest]
  79.             self.maxHeapify(largest, n)
  80.  
  81.     def buildMaxHeap(self):
  82.         for i in range(len(self._l)/2 - 1, -1, -1):
  83.             self.maxHeapify(i, len(self._l)-1)
  84.  
  85.     def heapMax(self):
  86.         """Returns the largest node"""
  87.         if len(self._l) <= 0:
  88.             return None
  89.         return self._l[0]
  90.  
  91.     def extractMax(self):
  92.         """Removes and returns the largest node"""
  93.         if len(self._l) <= 0:
  94.             return None
  95.         self._l[0], self._l[len(self._l)-1] = self._l[len(self._l)-1], self._l[0]
  96.         self.maxHeapify(0, len(self._l)-2)
  97.         return self._l.pop()
  98.  
  99.     def increaseKey(self, i, key):
  100.         """Increase the value of a node"""
  101.         if self._l[i] > key:
  102.             return
  103.         self.l[i] = key
  104.  
  105.         while i > 0 and self._l[self.getParent(i)] < self._l[i]:
  106.             self._l[self.getParent(i)], self._l[i] = self._l[i], self._l[self.getParent(i)]
  107.             i = self.getParent(i)
  108.  
  109.     def insert(self, v):
  110.         import sys
  111.         self._l.append(-sys.maxint-1)
  112.         self.increaseKey(len(self._l)-1, v)
  113.  
  114.     def dequeue(self):
  115.         return self.extractMax()
  116.  
  117.     def enqueue(self, v):
  118.         self.insert(v)
  119.  
  120.     def __str__(self):
  121.         return str(self._l)
  122.  
  123. def main():
  124.     # Generate a random list
  125.     l = getRandomList()
  126.     print(l)
  127.  
  128.     # Build a priority queue
  129.     queue = PriorityQueue(l)
  130.     print(queue)
  131.  
  132.     # dequeue
  133.     m = queue.dequeue()
  134.     print(queue)
  135.  
  136.     # enqueue
  137.     queue.enqueue(10)
  138.     print(queue)
  139.  
  140. if __name__ == '__main__':
  141.     main()
  142.
Reference
  • CLRS Chapter 6.5