B-Heap vs. Binary Heap (2010)

This is a great article and the diagrams illustrating the difference between a binary heap and a B-heap are awesome. The comments are amusingly negative, too.<p>It's worth noting that it was published in 2010, though. The Wikipedia article on B-heaps actually references this article: <a href="http://en.wikipedia.org/wiki/B-heap" rel="nofollow">http://en.wikipedia.org/wiki/B-heap</a>

Thanks for the article and the comments, I had never heard of Cache Oblivious algorithms and this article seems to indicate that others have not either: <a href="http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx" rel="nofollow">http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-obli...</a><p>I wonder if current popular libraries like the STL or the Java Collections library have started to take advantage of this work yet or not...

Those of you interested in cache conscious algorithm design should check out Anthony LaMarca's thesis from 1996: <a href="http://homes.cs.washington.edu/~lamarca/pubs/lamarca-thesis.pdf" rel="nofollow">http://homes.cs.washington.edu/~lamarca/pubs/lamarca-thesis....</a><p>The article only cites papers from 1961 and 1964, and complains about how CS departments use out-of-date machine models when teaching algorithms. This is just not true at any of the top schools.

There's some useful comments from last time this popped on to the HN front page: <a href="http://news.ycombinator.com/item?id=1426211" rel="nofollow">http://news.ycombinator.com/item?id=1426211</a>

Here[0] is the implementation if anyone is curious.<p>[0] <a href="https://github.com/varnish/Varnish-Cache/blob/master/lib/libvarnish/binary_heap.c" rel="nofollow">https://github.com/varnish/Varnish-Cache/blob/master/lib/lib...</a>