CS 269S, Winter 2011: Theory Seminar
Bren Hall, Room 1427
4 Mar 2011:

Pairing Heaps: Where are they now?

Darren Strash, UC Irvine

The pairing heap is a meldable heap data structure by Fredman, Sedgewick, Sleater, and Tarjan, which is intended to be a practical alternative to Fibonacci heaps. Experimental analysis shows that pairing heaps meet their intended purpose: they are quite efficient in practice; however, a precise amortized analysis of pairing heaps has proved difficult. In this talk, I will discuss the pairing heap data structure and the progress that has been made toward its analysis. I conclude by discussing a variant of the pairing heap by Amr Elmasry ("Pairing Heaps with Costless Meld", ESA 2010) that matches known lower bounds.