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.