## DIMACS TR: 2001-30

## Scrambled pairing and square-root trees

### Authors: Amr Elmasry

**
ABSTRACT
**

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