# Finding a worst case of heap sort

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 ﬁle 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]

• are you basically asking "why my code is so slow"? I think this question is too localized, and anyways belongs better in Stack Overflow – Ran G. Apr 28 '12 at 3:43
• No, really, i want to find the worst case for the heapsort algorithm. But my code is a try to understand these cases. – jonaprieto Apr 28 '12 at 4:22
• 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) – Alex ten Brink Apr 28 '12 at 8:30
• This paper seems to be relevant. I second Ran; please edit the question so that it asks the question without boilerplate. – Raphael Apr 28 '12 at 9:24
• May be this is helpful. – user742 Apr 28 '12 at 21:23

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]

• But, these examples are not heaps! – jonaprieto Apr 30 '12 at 22:41