8
$\begingroup$

I'm working on problem H in the ACM ICPC 2004–2005 Northeastern European contest.

The problem is basically to find the worst case that produces a maximal number of exchanges in the algorithm (sift down) to build the heap.

  • Input: Input file contains $n$ ($1 \le n \le 50{,}000$).
  • Output: Output the array containing $n$ different integer numbers from $1$ to $n$, such that it is a heap, and when converting it to a sorted array, the total number of exchanges in sifting operations is maximal possible.

Sample input: 6
Corresponding output: 6 5 3 2 4 1

And the basics outputs:

[2, 1]   
[3, 2, 1]   
[4, 3, 1, 2] 
[5, 4, 3, 2, 1] 
[6, 5, 3, 4, 1, 2]
$\endgroup$
  • 2
    $\begingroup$ are you basically asking "why my code is so slow"? I think this question is too localized, and anyways belongs better in Stack Overflow $\endgroup$ – Ran G. Apr 28 '12 at 3:43
  • $\begingroup$ No, really, i want to find the worst case for the heapsort algorithm. But my code is a try to understand these cases. $\endgroup$ – jonaprieto Apr 28 '12 at 4:22
  • 2
    $\begingroup$ If you want to try heapsort on all possible orderings of arrays, then it's not very surprising your algorithm is extremely slow: it will have a running time of at least $\Omega(n!)$, which grows more than exponentially. 10! is already 3.6 million. You'd be better off with a theoretical analysis. (reposted comment as I misread the start of your question so the second part of my comment was not valid) $\endgroup$ – Alex ten Brink Apr 28 '12 at 8:30
  • $\begingroup$ This paper seems to be relevant. I second Ran; please edit the question so that it asks the question without boilerplate. $\endgroup$ – Raphael Apr 28 '12 at 9:24
  • $\begingroup$ May be this is helpful. $\endgroup$ – user742 Apr 28 '12 at 21:23
4
$\begingroup$

Given the worst-case for $n$, we can construct the worst-case for $n+1$ as follows: we do a 'swap cycle' as follows: we take $n+1$, put it in $a[0]$, and we swap $a[0]$ with the maximal element of its children, which is $a[1]$ or $a[2]$, which we again swap with the maximum element of its children and so on, until we leave the $n$-element heap, at which point we put that last element at the $n+1$-th position.

An example: the worst-case for $n=5$ is $[5, 4, 3, 2, 1]$. We swap in 6 which creates the heap $[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1]$, after which we end up with 2, which we insert at the end: $[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1, \textbf{2}]$.

The above method works by induction: we start from the worst result for $n-1$ elements and perform a sift-down operation in reverse, maximizing the number of swaps it has to do ($\lfloor\log(n)\rfloor$ swaps). You can't do more swaps than this, so you maximize the number of swaps after the first extract-min operation, after which you are left with exactly the worst-case for $n-1$ elements for the next extract-min operation. This implies that the number of swaps is indeed maximal.

Note that this method gives different results than you have gotten:

[1]
[2, 1]
[3, 2, 1]
[4, 3, 1, 2]
[5, 4, 1, 3, 2]
[6, 5, 1, 4, 2, 3]
[7, 6, 1, 5, 2, 4, 3]
[8, 7, 1, 6, 2, 4, 3, 5]
[9, 8, 1, 7, 2, 4, 3, 6, 5]
[10, 9, 1, 8, 2, 4, 3, 7, 5 ,6]

However, both solutions are correct:

[5, 4, 1, 3, 2]
[2, 4, 1, 3| 5]
[4, 2, 1, 3| 5]
[4, 3, 1, 2| 5]
[2, 3, 1| 4, 5]
[3, 2, 1| 4, 5]

[5, 4, 3, 2, 1]
[1, 4, 3, 2| 5]
[4, 1, 3, 2| 5]
[4, 2, 3, 1| 5]
[1, 2, 3| 4, 5]
[3, 2, 1| 4, 5]

[6, 5, 1, 4, 2, 3]
[3, 5, 1, 4, 2| 6]
[5, 3, 1, 4, 2| 6]
[5, 4, 1, 3, 2| 6]
[2, 4, 1, 3| 5, 6]
[4, 2, 1, 3| 5, 6]
[4, 3, 1, 2| 5, 6]
[2, 3, 1| 4, 5, 6]
[3, 2, 1| 4, 5, 6]

[6, 5, 3, 4, 1, 2]
[2, 5, 3, 4, 1| 6]
[5, 2, 3, 4, 1| 6]
[5, 4, 3, 2, 1| 6]
[1, 4, 3, 2| 5, 6]
[4, 1, 3, 2| 5, 6]
[4, 2, 3, 1| 5, 6]
[1, 2, 3| 4, 5, 6]
[3, 2, 1| 4, 5, 6]
$\endgroup$
  • $\begingroup$ But, these examples are not heaps! $\endgroup$ – jonaprieto Apr 30 '12 at 22:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.