[theory-seminar] Theory Lunch 11/20: Thomas Hansen on Hollow Heaps

[Greg Bodwin]

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!
>
> 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/20141120/73b330b7/attachment.html>