Finden eines schlimmsten Falles der Heap-Sortierung

Ich arbeite an Problem H im nordosteuropäischen Wettbewerb ACM ICPC 2004–2005 .

Das Problem besteht im Wesentlichen darin, den schlimmsten Fall zu finden, der eine maximale Anzahl von Austauschen im Algorithmus erzeugt (nach unten sieben), um den Heap zu erstellen.

• Eingabe: Die Eingabedatei enthält ( ).1 ≤ n ≤ $n$$1 \le n \le 50{,}000$
• Ausgabe: Gibt das Array mit verschiedenen Ganzzahlen von bis , sodass es sich um einen Heap handelt. Bei der Konvertierung in ein sortiertes Array ist die Gesamtzahl der Austausche bei Siebvorgängen maximal möglich.1 $n$$1$$n$

Beispieleingabe: 6
Entsprechende Ausgabe:6 5 3 2 4 1

Und die grundlegenden Ausgaben:

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

Wenn der Worst-Case für , können wir den Worst-Case für wie folgt konstruieren : Wir führen einen 'Swap-Zyklus' wie folgt durch: Wir nehmen , setzen ihn in und tauschen mit dem maximalen Element seiner Kinder, das oder , das wir wieder mit dem maximalen Element seiner Kinder tauschen und so weiter, bis wir den Element- Haufen an diesem Punkt verlassen Wir setzen das letzte Element an die te Position.n + 1 n + 1 a [ 0 ] a [ 0 ] a [ 1 ] a [ 2 ] n n + $n$$n+1$$n+1$$a[0]$$a[0]$$a[1]$$a[2]$$n$$n+1$

Ein Beispiel: Der schlechteste Fall für ist . Wir tauschen 6 ein, wodurch der Heap wird. wir 2, die wir am Ende einfügen: .[ 5 , 4 , 3 , 2 , 1 ] [ 6 , 5 , 3 , 4 , 1 ] [ 6 , 5 , 3 , 4 , 1 , 2$n=5$$[5, 4, 3, 2, 1]$$[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1]$$[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1, \textbf{2}]$

Die obige Methode funktioniert durch Induktion: Wir gehen vom schlechtesten Ergebnis für Elemente aus und führen eine Sift-Down-Operation in umgekehrter Reihenfolge durch, um die Anzahl der erforderlichen Swaps zu maximieren ( Swaps). Sie können nicht mehr Swaps als diese ausführen, sodass Sie die Anzahl der Swaps nach der ersten Extraktions-Min-Operation maximieren. Danach bleibt für die nächste Extraktions-Min-Operation genau der schlechteste Fall für Elemente übrig . Dies bedeutet, dass die Anzahl der Swaps tatsächlich maximal ist.⌊ log ( n ) ⌋ n - $n-1$$\lfloor\log(n)\rfloor$$n-1$

Beachten Sie, dass diese Methode andere Ergebnisse liefert als Sie erhalten haben:

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

Beide Lösungen sind jedoch richtig:

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