News for hackers. Stuff that matters.
Re:You're Doing It Wrong: CS in the real world by gojomo on Saturday June 12, 2010 @01:46PM (#1426279)
Does the 'B-heap' PHK describes already have a name in the literature?
Re:You're Doing It Wrong: CS in the real world by kenjackson on Saturday June 12, 2010 @02:20PM (#1426309)
Not that I know of, but there are a LOT of heap variants in the literature, and I'm not clear on the details of the OPs algorithm (it gave an overview, but not as detailed as most in the literature)

The work by Arge, et al is probably the foundational work in priority queues for modern memory hierarchies. If I recall correctly, they use a cache oblivious approach: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106....

That's a good start if you're looking at the literature.

Re:You're Doing It Wrong: CS in the real world by mad on Saturday June 12, 2010 @02:48PM (#1426348)
It's the van Emde Boas layout. For example, see here http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-obli....
Re:You're Doing It Wrong: CS in the real world by ssp on Saturday June 12, 2010 @02:56PM (#1426360)
No, it's not. The van Emde Boas layout splits the data set into sqrt(n) chunks of sqrt(n) items. Then it recursively splits each of those chunks similarly.

This version simply divides the data set into page sized chunks. That has worse memory access complexity than the van Emde Boas layout, but is likely simpler to deal with in practice. It's not trivial to maintain the van Emde Boas layout under insertion and deletion for example.

(The post you link is a good one btw.)