2013/02/26 by John Iacono, Iacono, John
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #E.1 #FOS: Computer and information sciences #Natural Language Processing Techniques #Network Packet Processing and Optimization #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.1302.6641
openalex publication_date 2013/02/26 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
A lower bound is presented which shows that a class of heap algorithms in the\npointer model with only heap pointers must spend Omega(log log n / log log log\nn) amortized time on the decrease-key operation (given O(log n) amortized-time\nextract-min). Intuitively, this bound shows the key to having O(1)-time\ndecrease-key is the ability to sort O(log n) items in O(log n) time; Fibonacci\nheaps [M.L. Fredman and R. E. Tarjan. J. ACM 34(3):596-615 (1987)] do this\nthrough the use of bucket sort. Our lower bound also holds no matter how much\ndata is augmented; this is in contrast to the lower bound of Fredman [J. ACM\n46(4):473-501 (1999)] who showed a tradeoff between the number of augmented\nbits and the amortized cost of decrease-key. A new heap data structure, the\nsort heap, is presented. This heap is a simplification of the heap of Elmasry\n[SODA 2009: 471-476] and shares with it a O(log log n) amortized-time\ndecrease-key, but with a straightforward implementation such that our lower\nbound holds. Thus a natural model is presented for a pointer-based heap such\nthat the amortized runtime of a self-adjusting structure and amortized lower\nasymptotic bounds for decrease-key differ by but a O(log log log n) factor.\n