Given n items, finding the “best” k of them is a common problem in games. This could be the k closest enemies, the k most important textures to be streamed next, the k least important entities to unload, or many other problems. Here we look at a neat algorithm for doing this in O(n·log(k)) time, and O(k) memory, the “Limited Heap”. O(n·log(k)) time is good, though not necessarily the best possible, but the O(k) storage is better than just “ok”, its very good.

Evgeniy Gabrilovich and Alex Gontmakher, first presented this algorithm in the Dr Dobb’s Journal article, “Heap Ltd.”, June 2003 (