next up previous contents
Next: Node refill strategy Up: B-heaps Previous: B-heaps

The data structure

The idea (presented in [6]) takes inspiration from B-trees and allows the nodes of the heap to be incomplete. One may say that instead of having only one extract buffer for the whole heap, every node in the heap is used as an extract buffer for its descendants. The function of the insert buffer is left unchanged.



Jesper Bojesen
Wed Nov 4 15:35:15 MET 1998