B堆
外观
B堆(英语:B-heap)是一个用来保证子树在一个内存页的二叉堆。这样可以在使用虚拟内存时减少访问很大堆时内存页的访问。传统的实现中,元素位置的映射(几乎)每一级都放在不同的内存页中。
也有其他非常高效实用虚拟内存和缓存的堆的变种,例如缓存忽略算法、k堆、[1]和van Emde Boas树。[2]
参见
[编辑]参考文献
[编辑]- ^ Naor, Dalit; Martel, Charles U.; Matloff, Norman S. Performance of Priority Queue Structures in a Virtual Memory Environment. Comput. J. 1991, 34 (5): 428–437. doi:10.1093/comjnl/34.5.428.
- ^ van Emde Boas, P.; Kaas, R.; Zijlstra, E. Design and implementation of an efficient priority queue. Mathematical Systems Theory. 1976, 10: 99–127. doi:10.1007/BF01683268.[失效链接]
外部链接
[编辑]- 实现: https://archive.today/20130416023425/http://www.varnish-cache.org/trac/browser/lib/libvarnish/binary_heap.c and http://phk.freebsd.dk/B-Heap/binheap.c(页面存档备份,存于互联网档案馆)
- Generic heap implementation with B-heap support(页面存档备份,存于互联网档案馆).
- 更多参见:van Emde Boas layouts see Benjamin Sach Descent into Cache-Oblivion(页面存档备份,存于互联网档案馆) or Cache-oblivious data structures(页面存档备份,存于互联网档案馆).
![]() | 这是一篇计算机科学小作品。您可以通过编辑或修订扩充其内容。 |