Figures 2 and 3 compare the calendar queue hold time to the hold time for splay tree and linear linked list priority queue implementations.
Figure 2 shows that on the Harris minicomputer the calendar queue hold time becomes smaller than the splay tree hold time when the queue size reaches 20, and stays smaller as the queue grows.
Binomial queues, pagodas, skew heaps, pairing heaps, and splay trees run with O(log n) time per hold operation.
The splay tree, a self-adjusting form of binary search tree that Danny Sleator and I developed, is one such data structure.
In a splay tree, each retrieval of an item is followed by a restructuring of the tree, called a splay operation.
As Figure 7 suggests, a sequence of costly retrievals in an originally very unbalanced splay tree will quickly drive it into a reasonably balanced state.
The invention of splay trees arose out of work 1 did with two of my students, Sam Bent and Danny Sleator, at Stanford in the late 1970s.
On the basis of these results, Danny and I conjecture that splay trees are a universally optimum form of binary search tree in the following sense: Consider a fixed set of n items and an arbitrary sequence of m [is greater than or =] n retrievals of these items.
In addition to their intriguing theoretical properties, splay trees have potential value in practice.
Since the addition of a DeleteMax operation to the splay tree implementation of a priority queue requires no change to either the basic data structure or the Insert and DeleteMin algorithms, I would expect the splay tree implementation of a generalized priority queue to perform as well or better than min-max heaps.
Lacking this, an empirical test of my hypothesis about the relative performance of splay trees and min-max heaps must rest on their use in particular applications.