The rough gist is that if the only thing you need to be able to do is insert and pop-min, then you can buffer up roughly a page's worth of incomplete work for each page, getting amortized performance that tracks the optimal number of cache transfers at each level of the cache.
Further, in the paper above you are introduced (in the related work) to the citation:
"A. LaMarca and R. E. Ladner. The influence of caches on the performance of heaps. Journal of Experimental Algorithmics, 1, 1996."
which describes the author's "B-Heap" (at least, it describes a b-ary heap where you pick b to match your cache line/page size).
I'm guessing the problem isn't that academics don't understand these things so much that practicing programmers don't always read very much.
http://erikdemaine.org/papers/BufferTrees_STOC2002/paper.pdf
The rough gist is that if the only thing you need to be able to do is insert and pop-min, then you can buffer up roughly a page's worth of incomplete work for each page, getting amortized performance that tracks the optimal number of cache transfers at each level of the cache.
Further, in the paper above you are introduced (in the related work) to the citation:
"A. LaMarca and R. E. Ladner. The influence of caches on the performance of heaps. Journal of Experimental Algorithmics, 1, 1996."
which describes the author's "B-Heap" (at least, it describes a b-ary heap where you pick b to match your cache line/page size).
I'm guessing the problem isn't that academics don't understand these things so much that practicing programmers don't always read very much.