Search Mailing List Archives
[theory-seminar] Theory Lunch 11/20: Thomas Hansen on Hollow Heaps
Greg Bodwin
greg.bodwin at gmail.com
Mon Nov 17 19:39:49 PST 2014
As usual, we will have food at 12:15 and a talk at 12:30. Gates 4b wing
lobby. See you there!
Greg
---------
Title: Hollow Heaps
Abstract:
We introduce the hollow heap, a very simple data structure that matches the
performance of the classical Fibonacci heaps. Hollow heaps have the
following advantages over Fibonacci heaps:
(i) Each heap is represented by a single heap-ordered tree, instead of a
set of trees.
(ii) The outcomes of all comparisons are explicitly represented in the
data structure, so none are wasted.
(iii) Decrease-key operations are particularly simple: each one takes O(1)
time worst-case and does no cuts.
(iv) Each node in a hollow heap has only three pointers: no parent pointers
are needed, and lists of children are singly linked.
Hollow heaps obtain their efficiency by using lazy deletion to do
decrease-key operations. This leaves hollow nodes in the data structure,
i.e., nodes that do not contain items, giving the data structure its name.
Joint work with Haim Kaplan, Robert E. Tarjan, and Uri Zwick.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20141117/f9aa2155/attachment.html>
More information about the theory-seminar
mailing list