B-heap

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A B-heap is a binary heap implemented to keep subtrees in a single page. This reduces the number of pages accessed by up to a factor of ten for big heaps when using virtual memory, compared with the traditional implementation.[1] The traditional mapping of elements to locations in an array puts (almost) every level in a different page.

There are other heap variants which are efficient in computers using virtual memory or caches, such as cache-oblivious algorithms, k-heaps,[2] and van Emde Boas layouts.[3]

See also[edit]

References[edit]

  1. ^ Kamp, Poul-Henning (June 11, 2010). "You're Doing It Wrong". ACM Queue. 
  2. ^ Naor, Dalit; Martel, Charles U.; Matloff, Norman S. (1991). "Performance of Priority Queue Structures in a Virtual Memory Environment". Comput. J. 34 (5): 428–437. doi:10.1093/comjnl/34.5.428.  edit
  3. ^ van Emde Boas, P.; Kaas, R.; Zijlstra, E. (1976). "Design and implementation of an efficient priority queue". Mathematical Systems Theory 10: 99–127. doi:10.1007/BF01683268.  edit

External links[edit]