In this talk I survey the theoretical performance of various heap structures on cached and paged memory, and report the results of some practical experiments carried out by ourselves and others. The main conclusion of this study is that external-memory heap structures behave well also in internal memory. As a further conclusion it might be necessary to revise the contents of undergraduate courses on data structures and algorithms to include external-memory data structures.

(This is joint work with Jesper Bojesen.)

Host: Joan Boyar