Putting your data structure on a diet
Authors:Hervé Brönnimann, Jyrki Katajainen, and Pat Morin
Published in:Proceedings of the 6th STL Workshop, CPH STL Report 2006-8, Department of Computer Science, University of Copenhagen (2006), 3
Full text:<pdf.gif>PDF (735 kB)  

Consider a data structure D that stores a dynamic collection of elements. Assume that D uses a linear number of words in addition to the elements stored. In this paper several data-structural transformations are described that can be used to transform D into another data structure D′ that supports the same operations as D, has considerably smaller memory overhead than D, and performs the supported operations by a small constant factor or a small additive term slower than D, depending on the data structure and operation in question. The compaction technique has been successfully applied for linked lists, dictionaries, and priority queues.

Related:<html.gif>HTML (Technical report)  
  author = {Herv\'{e} Br\"{o}nnimann and Jyrki Katajainen and Pat Morin},
  title = {Putting your data structure on a diet},
  booktitle = {Proceedings of the 6th STL Workshop},
  series = {CPH STL Report},
  volume = {2006-8},
  publisher = {Department of Computer Science, University of Copenhagen},
  year = {2006},
  pages = {3},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.