An n-node forest of trees is called a square-root forest, if it has the following structure. For a given positive integer $k$ the forest has $2k$ trees. The first $k+1$ are single nodes. For the other $k-1$ trees, the root of tree $l$ has $l$ single-node children, for all $l$ from 1 to $k-1 $. If $n \neq k+\frac{k \; (k+1)}{2}$ the definition is slightly different.
Given a forest of $\tau$ trees, the rank of a tree is defined to be the number of children of the root of this tree. A phase of operations is defined as first linking the trees in pairs, then replacing the tree with the largest rank with its sub-trees together with a new single-node tree. The pairing is done by first sorting the trees by rank and numbering them from $1$ to $\tau$, then linking the root of tree $l$ to the root of tree $l+\lceil \tau/2 \rceil$, for all $l$ from $1$ to $\lfloor \tau/2 \rfloor$. We give a combinatorial proof that after applying an $O(n^{1.5})$ phases, the forest will converge to the square-root forest.
It is proven in \cite{fsst} that using any pairing strategy, the amortized
cost of deleting the item with the minimum value from a heap is
$O(\sqrt{n})$. Our pairing strategy gives $\Theta(\sqrt{n})$ amortized
cost for this operation.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-30.ps.gz
DIMACS Home Page