Problems 21-1: Off-line minimum(Page 517 of CLRS)
    The off-line minimum problem asks us to maintain a dynamic set of elements from the domain under the operations INSERT and EXTRACT-MIN. We are given a sequence S of n INSERT and m EXTRACT-MIN calls, where each key in is inserted exactly once. We wish to determine which key is returned by each EXTRACT-MIN call. Specifically, we wish to fill in an array , where for is the key returned by the th EXTRACT-MIN call. The problem is "off-line" in the sense that we are allowed to process the entire sequence before determining any of the returned keys.

In the following instance of the off-line minimum problem, each INSERT is represented by a number and each EXTRACT-MIN is represented by the letter :

Fill in the correct values in the extracted array.

To develop an algorithm for this problem, we break the sequence into homogeneous subsequences. That is, we represent by

where each represents a single EXTRACT-MIN call and each represents a (possibly empty) sequence of INSERT calls. For each subsequence , we initially place the keys inserted by these operations into a set , which is empty if is empty. We then do the following.

Argue that the array returned by OFF-LINE-MINIMUM is correct.

Describe how to implement OFF-LINE-MINIMUM efficiently with a disjoint-set data structure. Give a tight bound on the worst-case running time of your implementation.

Solutions:

a) the array will hold .

b)We will show that the extracted array is correct by contradiction. Assume that the extracted array is not correct. Let = be the smallest value for which the extracted array is incorrect. Let the correct solution reside in the array correct. Call the value of . We have two cases, one where and one where We will prove that neither case can occur.

Assume that . Then the element can’t appear in the extracted array, or it would have been the smallest value for which the extracted array was incorrect.Since we’ve already processed before processing , it must have had a set value of . But, if was set to , then must initially have been in some with . Since had no value yet when we processed , then we couldn’t have put in set since we only union with the set above us and we haven’t unioned yet. Therefore, we can’t have .

Assume that . We argue that the element must appear in the correct array. Obviously must appear before the th extraction in the original sequence since the OFF-LINE-MINIMUM algorithm never moves sets of elements backwards, it only unions with sets later than it. If we hadn’t extracted by the th extraction,then the optimal solutions should have chosen instead of for the th extraction since is smaller. Therefore, the optimal solution must have extracted for some . But, that means that holds some . By similar reasoning as above, we couldn’t have moved past set since would have been empty at the time was chosen. So, since we only union with sets above us and hasn’t been unioned yet, we can’t put in before . Therefore, we can’t have .

Since we have shown that we must have = for all , the OFF-LINE-MINIMUM algorithm returns the correct array.

c)We can efficiently implement OFF-LINE-MINIMUM using a disjoint-set forest. We begin by creating sets, one for each number, using the MAKE-SET operation. Then, we call UNION times to create the sets, the sequences of insertions between extractions. For each set , we will also maintain 3 additional pieces of information, number, prev, and next in the representative element of the set (actually this information will be at all the elements, but it will only be maintained for the representative). number will correspond to and can easily be set with the initial creating of the sets. prev will point to the representative element of and next will point to the representative element of . We can maintain these three properties through unions as follows: when we union two sets and where is the next set that still exists after , we set number of the new representative equal to the maximum of the two representative numbers, in this case,. We set prev of the new set equal to prev of set and we set next of prev of equal to the new representative element. Similarly, we set next of the new set equal to next of set and we set prev of next of equal to the new representative element.

In the OFF-LINE-MINIMUM algorithm, each iteration of the for loop ( iterations) will first call FIND-SET on (line 2). We use the number field of the returned representative as . Then, in line 5, to determine the smallest greater than for which set exists, we can simply follow the next pointer from , which takes constant time. In line 6, we call UNION again, at most times throughout the iterations. For each UNION call, we follow the procedure above for updating the number, prev and next, all of which take constant time. Therefore, we have a total of MAKE-SET operations, FIND-SET operations, and UNION operations. Since we have total operations and MAKE-SET operations, we know that the worst-case running time is .