Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[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