Hollow Heaps

Authors:

Abstract
We introduce the hollow heap , a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete - min take O (1) time, worst case as well as amortized; delete and delete - min take O (log n ) amortized time on a heap of n items. Hollow heaps are the simplest structure to achieve these bounds. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease - key operations and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. Lazy deletion produces hollow nodes (nodes without items), giving the data structure its name.
Funding Information
  • Danmarks Grundforskningsfond (61061130540)
  • German-Israeli Foundation for Scientific Research and Development (1161/2011)
  • United States - Israel Binational Science Foundation (2012338)
  • National Natural Science Foundation of China (61061130540)
  • Israeli Centers of Research Excellence (Center No. 4/11)
  • Natur og Univers, Det Frie Forskningsråd (12-126512)
  • Israel Science Foundation (822-10 and 1841/14)

This publication has 20 references indexed in Scilit: