Priority Queues (or heaps) consist of a set of items, each with a real-valued key, and provide the following operations:
- Clear() clears the priority queue, removing all items.
- Insert(item, key) inserts the passed item with the specified key into the priority queue.
- FindMin() returns the item with the minimum key in the priority queue.
- DeleteMin() deletes and returns the item with the minimum key in the priority queue.
- DecreaseKey(item, delta) decreases the key of the specified item in the priority queue by subtracting the passed non-negative real number delta.
- DecreaseKeyTo(item, newKey) decreases the key of the specified item in the priority queue to the passed non-negative real number.
- Delete(item) deletes the specified item from the priority queue.
My implementation is based on Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms by Michael L. Fredman and Robert Endre Tarjan. Given a heap with n items, deleting an arbitrary item is done in O(log n) amortized time. All other heap operations are performed in O(1) amortized time.
Fast heaps are incredibly helpful for speeding up pathfinding algorithms such as Dijkstra and A*.