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

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]

StackExchange Computer Science Q#1540, answer score: 4