[Python] Random Access Priority Queue
We describe a priority queue data structure that allows item removal via key or removal via (lowest) priority. As a bonus, there is code that shows how to implement a wrapper for a decorator class that enables per-method parameters and has access to class variables.
Random Access Priority Queue
The RandomAccessPriorityQueue class pairs a heap with a dictionary and provides O(log(n)) insertion and removal.
The heap is implemented with a python list, where left and right children are computed as a function of the index: for an item at index , the left child has index ; the right child, index .
The dictionary maintains a mapping from the key to the index location in the array.
Items are inserted and removed from the last position in the the array. On insertion, the new item is then ‘bubbled up,’ swapped with its parent until the priority of the new node is no longer less than the priority of the parent—the priority invariant.
On removal, the item to be removed is recursively swapped with the child having lower priority until reaching a leaf node. Then, the item to be removed is swapped with the last item in the list and returned. The previously last item in the list is then ‘bubbled up’ at its new location until the priority invariant is satisfied.
/blog/assets/2016-10-05-random-access-priority-queue/RandomAccessPriorityQueue.py:
... source file not found: /home/deploy/blog-redirect/releases/20190828224524/blog/assets/2016-10-05-random-access-priority-queue/RandomAccessPriorityQueue.py...An Example
Add ‘A’ with priority 9:
Add ‘B’ with priority 3:
Add ‘C’ with priority 0:
Add ‘D’ with priority 6:
Add ‘E’ with priority 5:
Add ‘F’ with priority 2:
Add ‘G’ with priority 4:
Add ‘H’ with priority 7:
Add ‘I’ with priority 1:
Add ‘J’ with priority 8:
Remove the lowest priority:
Remove ‘E’:
Remove ‘A’:
Remove ‘B’:
Remove the lowest priority:
Remove the lowest priority:
Remove the lowest priority:
Remove the lowest priority:
PriorityItem Abstract Class
RandomAccessPriorityQueue allows insertion of objects subclassed from the abstract PriorityItem class. However, in order to maintain consistency across less-than comparitors, all items must be of the same declared subclass.
/blog/assets/2016-10-05-random-access-priority-queue/PriorityItem.py:
... source file not found: /home/deploy/blog-redirect/releases/20190828224524/blog/assets/2016-10-05-random-access-priority-queue/PriorityItem.py...An example, non-abstract subclass:
/blog/assets/2016-10-05-random-access-priority-queue/MyItem.py:
... source file not found: /home/deploy/blog-redirect/releases/20190828224524/blog/assets/2016-10-05-random-access-priority-queue/MyItem.py...The Pydot Decorator Class
This is perhaps the most interesting piece of this article. We want to allow the user to set the PYDOT_DEBUG class variable of the RandomAccessPriorityQueue class. Setting this class variable is trivial. However, accessing the class variable from a decorator requires a decorator class which must be callable, i.e. it must implement the __call__ method.
However, the decorator class should also implement the __get__ method in order to set up proper bindings. This latter task is done through a lambda function which calls the PydotBeforeAfter instance passing ‘extra’ parameters, in our case the owner. The newly defined lambda function is then returned to the caller with the appropriate bindings and the expected parameter definitions. When the lambda function is called, it recovers the context of the closure and is able to pass the owner variable to the PydotBeforeAfter __call__ method.
Finally, we write a wrapper class that allows us to pass an extra tag, specific to each method decorated, so as to keep the output figures organized.
/blog/assets/2016-10-05-random-access-priority-queue/PydotBeforeAfter.py:
... source file not found: /home/deploy/blog-redirect/releases/20190828224524/blog/assets/2016-10-05-random-access-priority-queue/PydotBeforeAfter.py...