next up previous contents
Next: B-heaps Up: Summary Previous: A Hackers guide to

What external heaps can not do

The external heap structures described in this chapter has some limitations.

The increasekey/decreasekey operations can not be implemented efficiently for elements not in the root page or insertion buffer, because buffering can be done here only.

The heap with holes is limited to sorting applications, because inserts after extractmax violates the heap-with-holes property in a non trivial way.

Jesper Bojesen
Sat Apr 3 18:07:59 METDST 1999