Cascade Heap: Towards Time-Optimal Extractions

摘要

Heaps are well-studied fundamental data structures, having myriads of applications, both theoretical and practical. We consider the problem of designing a heap with an "optimal" EXTRACT-MIN operation. Assuming an arbitrary linear ordering of keys, a heap with n elements typically takes O(log n) time to extract the minimum. Extracting all elements faster is impossible as this would violate the Omega(n log n) bound for comparison-based sorting. It is known, however, that is takes only O(n+k log k) time to sort just k smallest elements out of n given, which prompts that there might be a faster heap, whose EXTRACT-MIN performance depends on the number of elements extracted so far. In this paper we show that this is indeed the case. We present a version of heap that performs INSERT in O(1) time and takes only O(log* n + log k) time to carry out the k-th extraction (where log* denotes the iterated logarithm). All the above bounds are worst-case.