All Talk, All Action

Phew, finally some time to give an update! After having worked on a nice little mobile game for XYRALITY for about five months (post mortem follows), Christian and me are up to our necks adding the finishing touches to Startup Weekend Hamburg Gaming.

Apart from that, I’ve been supervising the Bachelor Thesis of Julian Löhr about Developing a Windows Driver for the Nintendo Wii Remote, which ended up in giving a talk about working with the Unreal Development Kit at the SRH Hochschule Heidelberg.

Finally, I’ve started teaching at the SAE Institute Hamburg: If you’re interested in Tool Development and/or Style & Design Principles, head over to my new teaching section and check out the slides and source code.

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