pboothe
commented
14 years ago It was that article, and another one that came along that prompted me to write this :)
But then, I lost my link to this article, and was worried that it was a random blog post, so thank you very much for linking me back to it.
I recently came across the following article which might fit in your related work somewhere (or it might not, but I figure passing it along can't hurt). It describes a variation on the binary heap that organizes the heap in a more VM-friendly way (fewer page faults), and shows some performance graphs demonstrating the improved performance on a real system.
If you want a high level understanding of their variation, skip all the text and just compare Figures 5 and 6.
HTML version: http://queue.acm.org/detail.cfm?id=1814327
Citation: http://portal.acm.org/citation.cfm?id=1814327