Linear algorithm for off-line minimum problem

Question

I've been reading a paper "A Linear Time Algorithm for Maximum Matchings in Convex, Bipartite Graphs" by Steiner and Yeomans. In this paper at some point they solve an off-line minimum problem that is stated as follows:

You are given an empty set $S$ and a sequence of $n$ $\textrm{INSERT}(i)$ and $m$ $\textrm{EXTRACT-MIN}$ calls. $\textrm{INSERT}(i)$ will insert a number no greater than $n$ into the $S$ (I think we can even claim that each number is inserted exactly once). And $\textrm{EXTRACT-MIN}$ will find minimum element from the $S$, delete it from the $S$ and return it. The problem is to determine sequence of results of $\textrm{EXTRACT-MIN}$ calls.

Paper authors don't provide an algorithm implementation for this problem and claim that this problem can be solved in $O(n)$ by referencing "Data Structures and Network Algorithms" by Tarjan.

I haven't found any mentions of off-line minimum problem in this book and all references I found on the internet reference a problem from "Introduction to Algorithms" by Cormen et al. But this problem is suggested to be solved using a disjoint-set data structure, which leads to $O(n\alpha(n))$ amortized complexity, which is clearly not $O(n)$ worst-case.

So my question: is there really a $O(n)$ algorithm for this problem or is it a some mistake in the paper?

Answer 1

The paper "A linear-time algorithm for a special case of disjoint set union" (1983) by Gabow and Tarjan gives an $O(m+n)$ time algorithm to process $m$ union and find operations on $n$ elements, under the condition that the union tree is given as well. The union tree is a rooted tree where the vertices initially are labelled with the individual elements, and the union operations replace two adjacent vertices by a single vertex with the set union as its label, contracting the edge.

Note that in the algorithm of exercise in Cormen et al. you mention (as well as the algorithm from the book referenced in the Gabow and Tarjan paper), the union operations are described by a union tree where each initial set has an edge to its predecessor and successor in the sequence of extract-min/insert operations. This means we can apply the algorithm from Gabow and Tarjan to perform the union-find operations in the offline-min algorithm, and obtain an algorithm that runs in linear time.