Packages developed during research of heap structure implementations in python for CS380 at the University of Auckland.
A heap based priority queue implementation to demonstrate improvements over the standard Python library heapq by tracking element positions using a dictionary.
Feature improvements:
- O(1) lookup of any key's current priority with HeapQueue.get_priority(key)
- O(logn) modification of the priority for any key already in the heap
- O(logn) arbitrary element deletion with HeapQueue.remove(key)
Note: Although better asymptotic worst cases than standard the library, HeapQueue will be slower in most real world applications because of abstraction overhead and not currently having a C implementation.
An implementation of the dijkstra path finding algorithm as an example application for HeapQueue.
This is the standard heap based priority queue library with the C importing removed. Used to better compare speeds/operations with the custom HeapQueue class.
A better implementation of the _siftup function from heapq. The standard _siftup implementation in heapq does many unneeded operations which this version shows is not needed.
Developed for and tested with Python 3.8