commit | bd25317ebe041d88e7ed67d0b99d2fa3b29e9e25 | [log] [tgz] |
---|---|---|
author | Christian Hergert <christian@hergert.me> | Sun May 04 19:44:26 2014 +0200 |
committer | Christian Hergert <christian@hergert.me> | Sun May 04 19:44:26 2014 +0200 |
tree | 9d189d097a7315865ac8858f11157f98b1d8be1f | |
parent | b2825257449446313265842920c35262f35d9063 [diff] |
gheap: add GHeap for min heap based priority queues. This data structure allows for O(1) lookup time for one of min or max item (depending on a given compare function) in a priority queue. Insertion into the heap is O(log n) and removal from the heap is O(log n). It allows for removal from any index within the heap. Since the heap is implemented as an array, it can often have good cache locality properties.