Hollow Heaps

EADS Talk by Robert E. Tarjan, Princeton University.

Abstract

We introduce the hollow heap, a very simple data structure whose performance matches that of the classical Fibonacci heap. Hollow heaps have the following advantages over Fibonacci heaps:

  1. decrease-key operations are particularly simple: each one takes O (1) time worst-case and does no cuts.
  2. The outcomes of all comparisons are explicitly represented in the data structure, so none are wasted.
  3. Each node in a hollow heap has only three pointers: no parent pointers are needed, and lists of children are singly linked.

Hollow heaps combine two novel ideas. The rst is to use lazy deletion and re-insertion to do decrease-key operations. Such operations produce hollow nodes, i.e., nodes that do not contain items, giving the data structure its name. The second is to represent a heap by a dag (directed acyclic graph) instead of a tree or a set of trees.

About Tarjan: With hundreds of top publications, tens of thousands of authors citing his work, and as a Turing Award Winner (the computer science Nobel prize) professor Tarjan is recognized as world leading computer scientist. His work on graph algorithms and data structures has been addressing fundamental problems, giving  theoretical optimal solutions, with huge practical impact, and often also so elegant finding its way to standard text books. Among other things Tarjan has produced nearest common ancestors algorithms, and is co-inventor of both splay trees and Fibonacci heaps.