ICS Theory Group

May 14, Spring Quarter 2010: Theory Seminar

1:00pm in ICS 243

A Simpler Implementation and Analysis of Chazelle's Soft Heaps

Darren Strash

Presenting a SODA 2009 paper by Haim Kaplan and Uri Zwick

Abstract: The Soft Heap is an approximate, meldable priority queue created by Bernard Chazelle. The idea is genius: allow a fraction of the items inserted into the priority queue to have their keys artificially increased (corrupted), and in exchange, we get fast operations. We describe a new, simpler implementation of the Soft Heap, and discuss the clever ways that Soft Heaps have been used in the literature.