Grab Bag Release: Priority Queues

After having finished the Hamburg Relay Marathon with Christian, Nils and Florian yesterday, I’ve got a new part of my Grab Bag of Useful Stuff for you: Priority Queues.

This week we’ll be attending the Quo Vadis developer conference in Berlin. If you feel like chatting a little, just send me an e-mail and I’m sure we’ll find some time!

Priority Queues

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*.