Poul-Henning Kamp (creator of Varnish) recently published the B-heap algorithm. It's a cache-friendly version of the binary heap storage we all learned as freshmen.
PHK points out that mapping node n to nodes 2n and 2n+1 will cause cache misses (and often page faults) as we vertically descend the tree. So instead, rearrange the mapping so that the child nodes are often very near their parent node. That way, heap comparisons are usually performed in the same virtual page, which cuts-down on the number of disk accesses the operating system must perform.
PHK points out that mapping node n to nodes 2n and 2n+1 will cause cache misses (and often page faults) as we vertically descend the tree. So instead, rearrange the mapping so that the child nodes are often very near their parent node. That way, heap comparisons are usually performed in the same virtual page, which cuts-down on the number of disk accesses the operating system must perform.
http://queue.acm.org/detail.cfm?id=1814327