0
$\begingroup$

I've stumbled a heap-like sorting algorithm on the Internet as followed:

$\\$

For convenience, given a list of $2^n \; (n \in \mathbb{N^*})$ distinct numbers to be sorted increasingly.

Step 1: From the list, build a $P$-tree (to be defined) satisfying the min-heap property (Willard Zhan points out that this is actually a binomial heap), which costs $2^n-1$ comparisons. Go to Step 2.

Step 2: The root of the tree is the minimum on the tree at this time. So, pop it out and have $T$ trees remained. If $T > 1$, go to Step 3. If $T = 1$, go to Step 2. Otherwise, stop.

Step 3: By comparing their roots, join 2 of the remaining trees into 1 tree. The joining is done as followed: the larger root will be another child of the smaller root. The choice of 2 trees is done as followed: choose 2 trees with the least numbers of root's children. Continue joining until there is only 1 tree remained. One joining costs $1$ comparison, the whole step costs $T - 1$ comparisons ($T$ is taken from the previous step). Go to Step 2.

$P$-trees are defined as followed: $P_0$ is the $1$-node tree. For all positive integer $m$, $P_m$ is the tree having exactly $m$ first-class subtrees $P_0, ..., P_{m-1}$.

$\\$

I don't know this algorithm's proper name (if any). So I can't find any analysis on it, especially on its number of comparisons. I post this Question to ask for help on its name, its analysis, or some sources to read about them.

Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ Your P-tree is exactly the binomial heap. $\endgroup$ – Willard Zhan Jan 26 '17 at 9:29
  • $\begingroup$ I've clarified Step 3 a bit more. $\endgroup$ – Vincent J. Ruan Jan 26 '17 at 10:56
  • 2
    $\begingroup$ Look up the properties of the binomial heap and see whether you can analyze the algorithm yourself. $\endgroup$ – adrianN Jan 26 '17 at 12:16
  • $\begingroup$ With the "infinity" node, I've managed to proof an upper bound: $\; \; \; n(2^n-2)+1$ comparisons. However, so far I have no meaningful lower bound or the tight upper bound. $\endgroup$ – Vincent J. Ruan Jan 26 '17 at 14:42
  • $\begingroup$ I've proved a lower bound: $\; \; \; 2^{n+1}-3+\dfrac{(n-1)(n-2)}{2}$ comparisons. Despite having no tight bounds, for now, I'm satisfied with the analysis and suspending my effort. $\endgroup$ – Vincent J. Ruan Jan 26 '17 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.