Skew Heaps:Introduction and Basics of Amortized Analysis

Introduction

Priority Queue is one of the most extensively studied Abstract Data Types (ADT) due to its fundamental importance in the context of resource managing systems, such as operating systems. Priority Queues work on finite subsets of a totally ordered universal set U . With- out any loss of generality we assume that U is simply the set of all non-negative integers. In its simplest form, a Priority Queue supports two operations, namely,

• insert(x, S) : update S by adding an arbitrary x ∈ U to S.

• delete-min(S) : update S by removing from S the minimum element of S.

We will assume for the sake of simplicity, all the items of S are distinct. Thus, we assume that x /∈ S at the time of calling insert(x, S). This increases the cardinality of S, denoted usually by |S|, by one. The well-known data structure Heaps, provide an elegant

and efficient implementation of Priority Queues. In the Heap based implementation, bothinsert(x, S) and delete-min(S) take O(log n) time where n = |S|.

Several extensions for the basic Priority Queues were proposed and studied in response to the needs arising in several applications. For example, if an operating system maintains a set of jobs, say print requests, in a priority queue, then, always, the jobs with ‘high priority’ are serviced irrespective of when the job was queued up. This might mean some kind of ‘unfairness’ for low priority jobs queued up earlier. In order to straighten up the situation, we may extend priority queue to support delete-max operation and arbitrarily mix delete-min and delete-max operations to avoid any undue stagnation in the queue. Such priority queues are called Double Ended Priority Queues. It is easy to see that Heap is not an appropriate data structure for Double Ended Priority Queues. Several interesting alternatives are available in the literature [1] [3] [4]. You may also refer Chapter 8 of this handbook for a comprehensive discussion on these structures.

In another interesting extension, we consider adding an operation called melding. A meld operation takes two disjoint sets, S1 and S2, and produces the set S = S1 ∪ S2. In terms of an implementation, this requirement translates to building a data structure for S, given the data structures of S1 and S2. A Priority Queue with this extension is called a Meldable Priority Queue. Consider a scenario where an operating system maintains two different priority queues for two printers and one of the printers is down with some problem during operation. Meldable Priority Queues naturally model such a situation.

Again, maintaining the set items in Heaps results in very inefficient implementation of Meldable Priority Queues. Specifically, designing a data structure with O(log n) bound for each of the Meldable Priority Queue operations calls for more sophisticated ideas and approaches. An interesting data structure called Leftist Trees, implements all the operations of Meldable Priority Queues in O(log n) time. Leftist Trees are discussed in Chapter 5 of this handbook.

The main objective behind the design of a data structure for an ADT is to implement the ADT operations as efficiently as possible. Typically, efficiency of a structure is judged by its worst-case performance. Thus, when designing a data structure, we seek to minimize the worst case complexity of each operation. While this is a most desirable goal and has been theoretically realized for a number of data structures for key ADTs, the data structures optimizing worst-case costs of ADT operations are often very complex and pretty tedious to implement. Hence, computer scientists were exploring alternative design criteria that would result in simpler structures without losing much in terms of performance. In Chapter 13 of this handbook, we show that incorporating randomness provides an attractive alternative avenue for designers of the data structures. In this chapter we will explore yet another design goal leading to simpler structural alternatives without any degrading in overall performance. Since the data structures are used as basic building blocks for implementing algorithms,a typical execution of an algorithm might consist of a sequence of operations using the data structure over and again. In the worst case complexity based design, we seek to reduce the cost of each operation as much as possible. While this leads to an overall reduction in the cost for the sequence of operations, this poses some constraints on the designer of data structure. We may relax the requirement that the cost of each operation be minimized and perhaps design data structures that seek to minimize the total cost of any sequence of operations. Thus, in this new kind of design goal, we will not be terribly concerned with the cost of any individual operations, but worry about the total cost of any sequence of operations. At first thinking, this might look like a formidable goal as we are attempting to minimize the cost of an arbitrary mix of ADT operations and it may not even be entirely clear how this design goal could lead to simpler data structures. Well, it is typical of a novel and deep idea; at first attempt it may puzzle and bamboozle the learner and with practice one tends to get a good intuitive grasp of the intricacies of the idea. This is one of those ideas that requires some getting used to. In this chapter, we discuss about a data structure called Skew heaps. For any sequence of a Meldable Priority Queue operations, its total cost on Skew Heaps is asymptotically same as its total cost on Leftist Trees. However, Skew Heaps are a bit simpler than Leftist Trees.

Basics of Amortized Analysis

We will now clarify the subtleties involved in the new design goal with an example. Consider a typical implementation of Dictionary operations. The so called Balanced Binary Search Tree structure (BBST) implements these operations in O(m log n) worst case bound. Thus, the total cost of an arbitrary sequence of m dictionary operations, each performed on a tree of size at most n, will be O(log n). Now we may turn around and ask: Is there a data structure on which the cost of a sequence of m dictionary operations is O(m log n) but individual operations are not constrained to have O(log n) bound? Another more pertinent question to our discussion - Is that structure simpler than BBST, at least in principle? An affirmative answer to both the questions is provided by a data structure called Splay Trees. Splay Tree is the theme of Chapter 12 of this handbook.

Consider for example a sequence of m dictionary operations S1, S2, ..., Sm, performed using a BBST. Assume further that the size of the tree has never exceeded n during the sequence of operations. It is also fairly reasonable to assume that we begin with an empty tree and this would imply n ≤ m. Let the actual cost of executing Si be Ci. Then the total cost of the sequence of operations is C1 + C2 + ··· + Cm. Since each Ci is O(log n) we easily conclude that the total cost is O(m log n). No big arithmetic is needed and the analysis is easily finished. Now, assume that we execute the same sequence of m operations but employ a Splay Tree in stead of a BBST. Assuming that ci is the actual cost of Si in a Splay Tree, the total cost for executing the sequence of operation turns out to be c1 + c2 + ... + cm.

This sum, however, is tricky to compute. This is because a wide range of values are possible for each of ci and no upper bound other than the trivial bound of O(n) is available for ci. Thus, a naive, worst case cost analysis would yield only a weak upper bound of O(nm) whereas the actual bound is O(m log n). But how do we arrive at such improved estimates?

This is where we need yet another powerful tool called potential function.

The potential function is purely a conceptual entity and this is introduced only for the sake of computing a sum of widely varying quantities in a convenient way. Suppose there is a function f : D → R+ ∪ {0}, that maps a configuration of the data structure to a non-negative real number. We shall refer to this function as potential function. Since the data type as well as data structures are typically dynamic, an operation may change the configuration of data structure and hence there may be change of potential value due to this change of configuration. Referring back to our sequence of operations S1, S2,..., Sm, let Di−1 denote the configuration of data structure before the executing the operation Si and Di denote the configuration after the execution of Si. The potential difference due to this operation is defined to be the quantity f (Di) − f (Di−1). Let ci denote the actual cost of Si. We will now introduce yet another quantity, ai, defined by

If we are able to choose cleverly a ‘good’ potential function so that ai’s have tight, uniform bound, then we can evaluate the sum ), ai easily and this bounds the actual cost sum ), ci.

In other words, we circumvent the difficulties posed by wide variations in ci by introducing new quantities ai which have uniform bounds. A very neat idea indeed! However, care must be exercised while defining the potential function. A poor choice of potential function will result in ais whose sum may be a trivial or useless bound for the sum of actual costs. In fact, arriving at the right potential function is an ingenious task, as you will understand by the end of this chapter or by reading the chapter on Splay Trees.

The description of the data structures such as Splay Trees will not look any different from the description of a typical data structures - it comprises of a description of the organization of the primitive data items and a bunch of routines implementing ADT operations. The key difference is that the routines implementing the ADT operations will not be analyzed for their individual worst case complexity. We will only be interested in the the cumulative effect of these routines in an arbitrary sequence of operations. Analyzing the average potential contribution of an operation in an arbitrary sequence of operations is called amortized analysis. In other words, the routines implementing the ADT operations will be analyzed for their amortized cost. Estimating the amortized cost of an operation is rather an intricate task. The major difficulty is in accounting for the wide variations in the costs of an operation performed at different points in an arbitrary sequence of operations. Although our design goal is influenced by the costs of sequence of operations, defining the notion of amortized cost of an operation in terms of the costs of sequences of operations leads one nowhere. As noted before, using a potential function to off set the variations in the actual costs is a neat way of handling the situation.

In the next definition we formalize the notion of amortized cost.

DEFINITION 6.1 [Amortized Cost] Let A be an ADT with basic operations O = {O1, O2, ··· , Ok } and let D be a data structure implementing A. Let f be a potential function defined on the configurations of the data structures to non-negative real number. Assume further that f (Φ) = 0. Let Dl denote a configuration we obtain if we perform an operation Ok on a configuration D and let c denote the actual cost of performing Ok on D.

Then, the amortized cost of Ok operating on D, denoted as a(Ok , D), is given by

THEOREM 6.1 Let D be a data structure implementing an ADT and let s1, s2, ··· , sm denote an arbitrary sequence of ADT operations on the data structure starting from an empty structure D0. Let ci denote actual cost of the operation si and Di denote the configuration obtained which si operated on Di−1, for 1 ≤ i ≤ m. Let ai denote the amortized cost of si operating on Di−1 with respect to an arbitrary potential function. Then,

Therefore,

REMARK 6.1 The potential function is common to the definition of amortized cost of all the ADT operations. Since  holds good for any potential function, a clever choice of the potential function will yield tight upper bound for the sum of actual cost of a sequence of operations.