3 ms·
Does the 'B-heap' PHK describes already have a name in the literature?
by gojomo 16y ago
Does the 'B-heap' PHK describes already have a name in the literature?
- kenjackson 16y agoNot 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.3789 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.... That's a good start if you're looking at the literature.
- mad 16y agoIt's the van Emde Boas layout. For example, see here http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-obli....
- ssp 16y agoNo, 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.)