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
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> 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: <>

More information about the theory-seminar mailing list