# Linear algorithm for off-line minimum problem

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?

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.