This must be somewhat related an idea I read about recently. Indexing a binary heap other than the natural way can avoid cache misses and increase priority queue performance: http://playfulprogramming.blogspot.co.uk/2015/08/cache-optim...