DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                    UNIVERSITY OF SOUTHERN DENMARK, ODENSE                   

           From Internal to External Data Structures: Dynamic Heaps          

                               Jyrki Katajainen                              
                        Department of Computer Science                       
                           University of Copenhagen                          

                     Tuesday, April 11, 2000, at 2:15 PM                     
                               The Seminar Room                              


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