Cache-optimizing a priority queue

[ingve]

http://playfulprogramming.blogspot.com/2015/08/cache-optimizing-priority-queue.html

[sriram_malhar]

There is a well-known memory layout technique for a cache-oblivious tree called van Emde Boas layout.

https://en.wikipedia.org/wiki/Van_Emde_Boas_tree

[raymondh]

On a related note, the source code for Python demonstrates a practical way to cache-optimize the heapify() operation for the garden-variety heap implementation of a priority queue:

https://hg.python.org/cpython/file/6fd69aeb8a3b/Modules/_hea...