Skip to main content
To refer to this page use:
Abstract: We introduce the rank-pairing heap, an implementation of heaps that combines the asymptotic efficiency of Fibonacci heaps with much of the simplicity of pairing heaps. Other heap implementations that match the bounds of Fibonacci heaps do so by maintaining a balance condition on the trees representing the heap. In contrast to these structures but like pairing heaps, our trees can evolve to have arbitrary (unbalanced) structure. Also like pairing heaps, our structure requires at most one cut and no other restructuring per key decrease, in the worst case: the only changes that can cascade during a key decrease are changes in node ranks. Although our data structure is simple, its analysis is not.
Publication Date: 2011
Citation: Haeupler, Bernhard, Siddhartha Sen, and Robert E. Tarjan. "Rank-Pairing Heaps." SIAM Journal on Computing 40, no. 6 (2011): 1463-1485. doi:10.1137/100785351
DOI: 10.1137/100785351
ISSN: 0097-5397
EISSN: 1095-7111
Pages: 1463 - 1485
Type of Material: Journal Article
Journal/Proceeding Title: SIAM Journal on Computing
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.