Abstract

The soft heap is an approximate priority queue data structure originally proposed by Bernard Chazelle [Chazelle2000a]. Chazelle used it to develop the fastest deterministic comparison-based algorithm to compute a minimum spanning tree of a connected graph [Chazelle2000b]. The soft heap allows some items to become "corrupted", in which some keys are artificially increased. This allows us to overcome the sorting lower bound in the comparison-based model of computation, however, some of the corrupted items exit the heap out of order. The number of corrupted items in the heap is upper-bounded by epsilon*m, where epsilon is an error rate determined by the user, and m is the number of insertions into the heap. This corruption allows soft heap operations to run in constant amortized time for a suitable epsilon = O(1), making it ideal for applications where speed is prioritized over precision. Such applications include finding an approximate median of a set of items, and in dynamic maintenance of percentiles.

Chazelle's initial implementation of the soft heap uses a collection of binomial heaps. This was simplified in both implementation and analysis, by Kaplan and Zwick [KZ2009], and later by Kaplan, Zwick, and Tarjan [KTZ2013], both of which use binary heap-ordered trees instead. In this talk, I will discuss the design, and analysis of Kaplan, Zwick, and Tarjan's soft heap data structure, and its use in aforementioned applications. I will also briefly highlight some of my research interests in the field of algorithmic visualizations and expositions.

About the Speaker

I am a new instructor of computer science at Florida Institute of Technology. I received my Ph.D. from Clemson University under the supervision of Dr. Brian Dean in December 2016. I am fascinated by everything that involves algorithms. My research interests broadly include competitive programming, theoretical algorithms and data structures, graph theory, and computer science education. Lately, I am also venturing on projects that involve writing simple artificial intelligence agents to two player adversarial games.