Refined complexity analysis for heap operations

摘要

A heap (priority queue) is a data structure for representing a set of items, each item having an associated numerical value, which facilitates such operations as insertion, deletion, merge (union), and findmin (find the item having the minimum value). It is well known that when n items are present the inherent complexity of these operations (in terms of comparisons) is logn per operation in the worst case. However, Cheriton and Tarjan have observed that when the frequency of findmin operations is small relative to the frequency of other operations, then certain implementations of heaps perform better than logn per operation. We explore this phenomenon with respect to inherent complexity.