Das Sortieren in einem Haufen (es ist auch eine pyramidenförmige Sortierung) auf Habré wurde bereits mehr als ein- oder zweimal mit einem guten Wort in Erinnerung gerufen, aber dies waren immer recht bekannte Informationen. Jeder kennt den üblichen binären Heap, aber die Theorie der Algorithmen hat auch: einenn-Heap; ein Haufen Haufen basierend auf Leonardo-Zahlen; Deramid (eine Mischung aus Heap und binärem Suchbaum); Turnier Mini-Haufen; Spiegelhaufen (umgekehrt); schwacher Haufen; Jungs Haufen; Binomialstapel; und Gott weiß, welche anderen Haufen ...Und die klügsten Vertreter der Informatik in verschiedenen Jahren schlugen ihre Sortieralgorithmen unter Verwendung dieser Pyramidenstrukturen vor. Wen interessiert es, was sie getan haben? Für diejenigen, die sich mit dem Sortieren anhand dieser Strukturen befassen, beginnen wir mit einer kleinen Reihe von Artikeln. Die Welt der Haufen ist vielfältig - ich hoffe, Sie werden interessiert sein.
Dieser Artikel wurde mit Unterstützung von EDISON verfasst.
Wir beschäftigen uns mit der Entwicklung mobiler Anwendungen und bieten Softwaretests an .
Wir lieben die Theorie der Algorithmen! ;-);
Es gibt eine solche Klasse von Algorithmen - Sortieren nach Wahl. Die allgemeine Idee ist, dass der ungeordnete Teil des Arrays aufgrund der Tatsache reduziert wird, dass nach den maximalen Elementen gesucht wird, die von ihm in einen zunehmenden sortierten Bereich umgeordnet werden.Das Sortieren der üblichen Wahl ist Brute Force. Wenn es auf der Suche nach Maxima einfach ist, linear durch das Array zu gehen, kann die zeitliche Komplexität eines solchen Algorithmus O ( n 2 ) nicht überschreiten .Ein Bündel
Der effizienteste Weg, um mit den Höhen im Array zu arbeiten, besteht darin, die Daten in einer speziellen Baumstruktur zu organisieren, die als Heap bezeichnet wird . Dies ist ein Baum, in dem alle übergeordneten Knoten nicht weniger als untergeordnete Knoten sind.Andere Namen des Haufens - die Pyramide , der Sortierbaum .Schauen wir uns an, wie einfach und fast kostenlos es sein kann, ein Array in Form eines Baumes darzustellen.Nehmen Sie das allererste Element des Arrays und betrachten Sie, dass dies die Wurzel des Baums ist - ein Knoten der 1. Ebene. Die nächsten 2 Elemente sind Knoten der 2. Ebene, die rechten und linken Nachkommen des Wurzelelements. Die nächsten 4 Elemente sind Knoten der 3. Ebene, die rechten / linken Nachkommen des zweiten / dritten Elements des Arrays. Die nächsten 8 Elemente sind Knoten der 4. Ebene, Nachkommen von Elementen der 3. Ebene. Usw. In diesem Bild befinden sich die Knoten des Binärbaums deutlich unterhalb der entsprechenden Elemente im Array:Obwohl die Bäume in den Diagrammen bei einem solchen Scan häufiger dargestellt werden:Wenn Sie diesen Winkel betrachten, ist klar, warum das Sortieren nach einem Bündel als pyramidenförmiges Sortieren bezeichnet wird. Dies ist ungefähr so, als würde man einen Schachelefanten einen Offizier, einen Turm eine Tura und eine Königin eine Königin nennen.Indizes für die Nachkommen des i- ten Elements werden durch Elementar bestimmt (wenn der Index des ersten Elements des Arrays gleich 0 ist, wie es in den meisten Programmiersprachen üblich ist):Linker Nachkomme von 2 × i + 1,rechtes Kind: 2 × i + 2(ich bin in den Diagrammen und in Animationen beginnen die Indizes von Arrays traditionell mit 1, wobei die Formeln leicht unterschiedlich sind: linkes Kind: 2 × i und rechtes Kind: 2 × i + 1, aber das sind schon kleine arithmetische Nuancen).Wenn die aus diesen Formeln resultierenden Nachkommen die Indizes über das Array hinausgehen, bedeutet dies, dass das i- te Element keine untergeordneten Elemente hat. Es kann auch vorkommen, dass das i- te Element ein linker Nachkomme ist (fällt auf das letzte Element des Arrays, in dem eine ungerade Anzahl von Elementen vorhanden ist), aber es gibt kein rechtes.So kann jedes Array leicht in Form eines Baums dargestellt werden. Dies ist jedoch noch kein Heap, da im Array einige untergeordnete Elemente möglicherweise größer sind als ihre übergeordneten Elemente.Damit unser Baum, der auf der Grundlage des Arrays erstellt wurde, zu einem Haufen wird, muss er ordnungsgemäß gesiebt werden.Sichtung
Die Seele, einen Haufen zu sortieren, siebt.Das Sieben für ein Element ist, dass, wenn es kleiner als die Nachkommen ist, die in einer untrennbaren Kette zusammengefasst sind, dieses Element so niedrig wie möglich verschoben werden muss und größere Nachkommen 1 Ebene höher angehoben werden sollten.Das Bild zeigt den Siebpfad für das Objekt. Die blaue Farbe zeigt das Element an, für das gesiebt wird. Grün - größere Nachkommen den Ast hinunter. Sie werden eine Ebene höher angehoben, da sie größer sind als der blaue Knoten, für den der Bildschirm gemacht ist. Das Element selbst vom obersten blauen Knoten wird an die Stelle des untersten Nachkommen der grünen Kette verschoben.Ein Sieben ist erforderlich, um aus einem gewöhnlichen Baum einen Sortierbaum zu machen und den Baum in diesem (Sortier-) Zustand weiter zu unterstützen.In diesem Bild werden die Elemente des Arrays so neu verteilt, dass es bereits in einem Heap angeordnet ist. Obwohl das Array in einen Sortierbaum zerlegt wurde, wurde es noch nicht sortiert (entweder aufsteigend oder absteigend), obwohl alle Nachkommen im Baum kleiner als ihre übergeordneten Knoten sind. Aber dann ist das maximalste Element im Sortierbaum immer in der Hauptwurzel, was sehr wichtig ist.Heap Sort :: Heapsort
Der Algorithmus ist eigentlich einfach:- Stufe 1. Wir bilden einen Sortierbaum aus dem gesamten Array. Dazu gehen wir von rechts nach links über die Elemente (vom letzten zum ersten) und wenn das Element Nachkommen hat, machen wir ein Sieben dafür.
- 2. . , . ( ) . , .. . , — . , .
Python-Code für eine klassische pyramidenförmige Sortierimplementierung:
def HeapSort(data):
for start in range((len(data) - 2) / 2, -1, -1):
HeapSift(data, start, len(data) - 1)
for end in range(len(data) - 1, 0, -1):
data[end], data[0] = data[0], data[end]
HeapSift(data, 0, end - 1)
return data
def HeapSift(data, start, end):
root = start
while True:
child = root * 2 + 1
if child > end: break
if child + 1 <= end and data[child] < data[child + 1]:
child += 1
if data[root] < data[child]:
data[root], data[child] = data[child], data[root]
root = child
else:
break
Komplexität des Algorithmus
Warum ein einfacher Heap gut ist - er muss im Gegensatz zu anderen Baumarten nicht separat gespeichert werden (z. B. muss vor der Verwendung ein binärer Suchbaum erstellt werden, der auf einem Array basiert). Jedes Array ist bereits ein Baum, in dem Sie Eltern und Nachkommen sofort identifizieren können. Die Komplexität des zusätzlichen Speichers ist O ( 1 ), alles passiert sofort.Die Komplexität der Zeit hängt vom Sieben ab. Ein einzelnes Sieben wird in O (log n ) umgangen . Zuerst werden n Elemente durchsucht, um den anfänglichen Heap aus dem Array zu erstellen. Dieser Schritt erfordert O ( n log n ) . In der zweiten Phase, wenn wir n herausnehmenMit den aktuellen Maxima aus dem Heap wird der verbleibende unsortierte Teil, d. h. Diese Phase kostet uns auch O ( n log n ) .Gesamtzeitkomplexität: O ( n log n ) + O ( n log n ) = O ( n log n ).Darüber hinaus hat die Pyramidensortierung weder entartete noch bessere Fälle. Jedes Array wird mit einer angemessenen Geschwindigkeit verarbeitet, es gibt jedoch keine Verschlechterung oder Aufzeichnungen.Die Heap-Sortierung ist im Durchschnitt etwas langsamer als die schnelle Sortierung. Aber für Quicksort können Sie ein Killer-Array auswählen, an dem der Computer hängt, aber für Heapsort - nein.:: Ternary heapsort
Schauen wir uns den ternären Haufen an. Sie werden es nicht von binär glauben, es unterscheidet sich nur darin, dass die übergeordneten Knoten maximal nicht zwei, sondern drei Nachkommen haben. Im ternären Haufen für den i- ten Elementcode werden drei Nachkommen ähnlich berechnet (wenn der erste Elementindex = 0 ist):Der linke Nachkomme 3 × i + 1Mittlerer Nachkomme 3 × i + 2rechter Nachkomme 3 × i + 3(If Indizes beginnen mit 1, wie in den Animationen in diesem Artikel, dann müssen Sie in diesen Formeln nur eine subtrahieren.Sortiervorgang:Einerseits ist die Anzahl der Ebenen im Baum im Vergleich zum binären Heap spürbar reduziert, was bedeutet, dass beim Sieben im Durchschnitt weniger Swaps stattfinden. Um den minimalen Nachkommen zu finden, sind jedoch mehr Vergleiche erforderlich - da die Nachkommen jetzt nicht zwei, sondern drei sind. Im Allgemeinen in Bezug auf die zeitliche Komplexität - irgendwo finden wir, irgendwo verlieren wir, aber im Allgemeinen das Gleiche. Die Daten im ternären Heap sind etwas schneller sortiert als in der Binärdatei, aber diese Beschleunigung ist sehr gering. Bei allen Variationen der Pyramidensortierung bevorzugen die Entwickler der Algorithmen die binäre Option, da die Implementierung des Ternärs angeblich schwieriger ist (obwohl es "schwieriger" ist, dem Algorithmus ein paar oder drei zusätzliche Zeilen hinzuzufügen) und der Geschwindigkeitsgewinn minimal ist.Sortieren nach n-Heap Heap :: N-Narny Heapsort
Natürlich können Sie hier nicht aufhören und die Sortierung nach einer Reihe für eine beliebige Anzahl von Nachkommen anpassen. Wenn Sie die Anzahl der Nachkommen weiter erhöhen, können Sie möglicherweise die Geschwindigkeit des Prozesses erheblich erhöhen?Für das i- te Element der Array-Indizes (wenn die Anzahl Null ist) werden seine N Nachkommen sehr einfach berechnet:1. Nachkomme: N × i + 12. Nachkomme: N × i + 23. Nachkomme: N × i + 3...N-ter Nachkomme: N × i + NPython-Code zum Sortieren nach einem N-Heap:
def NHeapSort(data):
n = 3
for start in range(len(data), -1, -1):
NHeapSift(data, n, start, len(data) - 1)
for end in range(len(data) - 1, 0, -1):
data[end], data[0] = data[0], data[end]
NHeapSift(data, n, 0, end - 1)
return data
def NHeapSift(data, n, start, end):
root = start
while True:
child = root * n + 1
if child > end:
break
max = child
for k in range(2, n + 1):
current = root * n + k
if current > end:
break
if data[current] > data[max]:
max = current
if data[root] < data[max]:
data[root], data[max] = data[max], data[root]
root = max
else:
break
Mehr heißt jedoch nicht besser. Wenn Sie die Situation an ihre Grenzen bringen und N Nachkommen für ein Array von N Elementen verwenden, wird die Sortierung nach einer Gruppe zu einer Sortierung nach der üblichen Auswahl. Darüber hinaus wird es auch eine verschlechterte Version der Sortierung nach Auswahl geben, da sinnlose Gesten ausgeführt werden: Beim Sieben wird zuerst das Maximum an erster Stelle im Array gesetzt und dann das Maximum an das Ende gesendet (bei der Auswahlsortierung wird das Maximum sofort an das Ende gesendet).Wenn der ternäre Heap die Binärdatei minimal überholt, verliert das Vierfache bereits. Das Finden des maximalen Nachkommen unter mehreren wird zu teuer.Trailer der nächsten Serie
Der Hauptnachteil des binären / ternären / n-Heaps ist also, dass die Unfähigkeit, in seiner Komplexität zu springen, höher ist als O ( n log n ) . Der Ausweg aus dem Deadlock besteht darin, beim Sortieren anspruchsvollere Haufensorten zu verwenden. In einer Woche werden wir erfahren, was Edsger Dijkstra darüber denkt.Klicken Sie auf die Animation, um zum Artikel mit der folgenden Sortierung nach Bündeln zu gelangenVerweise
Haufen / PyramideSerienartikel:
AlgoLab-Anwendung hinzugefügt Sortierung nach n-Heap. Um die Anzahl der Nachkommen auszuwählen, müssen Sie im Kommentar zu der Zelle dieser Art eine Zahl für n angeben. Der Bereich möglicher Werte liegt zwischen 2 und 5 (dies ist nicht mehr sinnvoll, da für n> = 6 nicht garantiert ist, dass Animationen mit drei Verschachtelungsebenen in einem normalen Maßstab auf den Bildschirm passen).