Trouver le pire des cas de tri par tas

Je travaille sur le problème H dans le cadre du concours ACM ICPC 2004-2005 Europe du Nord-Est .

Le problème est essentiellement de trouver le pire cas qui produit un nombre maximal d'échanges dans l'algorithme (tamiser vers le bas) pour construire le tas.

• Entrée: le fichier d'entrée contient $n$ ($1 \le n \le 50{,}000$).
• Sortie: affiche le tableau contenant $n$ différents nombres entiers de $1$ à $n$, tel qu'il s'agit d'un tas, et lors de sa conversion en un tableau trié, le nombre total d'échanges dans les opérations de tri est maximal possible.

Exemple d'entrée: 6
Sortie correspondante:6 5 3 2 4 1

Et les sorties de base:

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

Étant donné le pire des cas pour $n$, nous pouvons construire le pire des cas pour $n+1$ comme suit: nous faisons un «cycle d'échange» comme suit: nous prenons $n+1$, mettre dans $a[0]$, et nous échangeons $a[0]$ avec l'élément maximal de ses enfants, qui est $a[1]$ ou $a[2]$, que nous échangeons à nouveau avec l'élément maximum de ses enfants et ainsi de suite, jusqu'à ce que nous quittions le $n$-élément tas, à quel point nous mettons ce dernier élément à la $n+1$-th position.

Un exemple: le pire des cas pour $n=5$ est $[5, 4, 3, 2, 1]$. On échange en 6 ce qui crée le tas$[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1]$, après quoi on se retrouve avec 2, que l'on insère à la fin: $[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1, \textbf{2}]$.

La méthode ci-dessus fonctionne par induction: on part du pire résultat pour $n-1$ éléments et effectuer une opération de tri vers le bas à l'envers, maximisant le nombre de swaps qu'il doit faire ($\lfloor\log(n)\rfloor$swaps). Vous ne pouvez pas faire plus de swaps que cela, donc vous maximisez le nombre de swaps après la première opération d'extraction min, après quoi vous vous retrouvez avec le pire cas pour$n-1$éléments pour la prochaine opération d'extraction min. Cela implique que le nombre de swaps est en effet maximal.

Notez que cette méthode donne des résultats différents de ceux que vous avez obtenus:

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

Cependant, les deux solutions sont correctes:

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