Search Mailing List Archives
[theory-seminar] Theory Lunch 11/20: Thomas Hansen on Hollow Heaps
greg.bodwin at gmail.com
Thu Nov 20 11:36:24 PST 2014
Reminder: In ~1 hour!
On Mon, Nov 17, 2014 at 7:39 PM, Greg Bodwin <greg.bodwin at gmail.com> wrote:
> As usual, we will have food at 12:15 and a talk at 12:30. Gates 4b wing
> lobby. See you there!
> Title: Hollow Heaps
> 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...
More information about the theory-seminar