（脱机最小值）脱机最小值问题（off-line minimu

（脱机最小值）脱机最小值问题（off-line minimum problem）是使用INSERT和EXTRACT-MIN操作维护一个元素取自域{1,2，...,n}的动态集合T。给定一组包含n个INSERT和m个EXTRACT-MIN的调用序列S，其中属于{1,2,...,n}中的每个关键字只被插入一次。我们希望确定每个EXTRACT-MIN调用返回的是哪个关键字。特别的，希望对一个extracted[1..m]（i=1,2,..,m）数组进行填充，其中extracted[i]是由第i次EXTRACT-MIN调用所返回的关键字。该问题是“脱机”的，其含义就是在确定任何返回的关键字之前处理整个序列S。

a.在下面脱机最小值问题的实例中，每个操作INSERT(i)用一个i值来表示，并且每个EXTRACT-MIN用字母E来表示：

                         4,8，E,3,E,9,2,6,E,E,E,1,7,E,5

   将正确的值填入extracted数组。

   为了设计出解决此问题的算法，我们把序列S划分成若干个同构的子序列，即如下表示S:

                      I1,E,I2,E,I3,...,I_m，E,I_m+1

这里每个E代表单次EXTRACT-MIN调用，并且每个Ij代表一个（可能为空的）INSERT调用序列，对于每个子序列Ij,开始时，把由这些操作插入的关键字插入一个集合Kj，如果Ij为空，那么它也为空，然后执行下面的程序：

OFF-LINE-MINIMUM(m,n)
1 for i=1 to n
2    determine j such that  3 if  4   extracted[j]=i
5   let l be the smallest value greater than j
        for which Kl exists
6    ,destroying Kj
7return extracted

b.证明：有OFF-LINE-EXTRACTED返回的数组extracted是正确的。

c.描述如何用不相交集合数据结构来高效实现OFF-LINE-MINIMUM。给出实现的最坏情况运行时间的精确界。