Get best of the week

Schwache Haufen-Sortierung


Von den gesamten Zoohaufen ist diese Struktur vielleicht die ungewöhnlichste. DarĂŒber hinaus passt die elegante Einfachheit des Algorithmus durchaus zu seiner erstaunlichen ExzentrizitĂ€t.

Beim Sortieren mit einem schwachen Heap gibt es immer weniger Vergleiche und Austausche als mit einem normalen Heap. Also ja, ein schwacher Stapel ist stÀrker als ein gewöhnlicher Stapel.
EDISON Software - Webentwicklung
Dieser Artikel wurde mit UnterstĂŒtzung von EDISON verfasst.

Wir beschÀftigen uns mit der Erstellung eingebetteter Software sowie der Entwicklung von Webanwendungen und Websites .

Wir lieben die Theorie der Algorithmen! ;-);

Schwacher Haufen


Ein regulĂ€rer Heap ist ein Sortierbaum, in dem ein Elternteil grĂ¶ĂŸer (oder gleich) ist als einer seiner Nachkommen. In einem schwachen Haufen wird diese Anforderung geschwĂ€cht - jeder Elternteil ist grĂ¶ĂŸer (oder gleich) als jeder Nachkomme nur von seinem rechten Teilbaum. Im linken Teilbaum können die Nachkommen sowohl kleiner als auch grĂ¶ĂŸer als die Eltern sein, da haben Sie so viel GlĂŒck.


Dieser Ansatz kann die Kosten fĂŒr die Aufrechterhaltung des Datensatzes in einem Heap-Zustand erheblich reduzieren. Schließlich muss sichergestellt werden, dass das Prinzip „ein Nachkomme ist nicht mehr als ein Elternteil“ nicht fĂŒr die gesamte Struktur, sondern nur fĂŒr die HĂ€lfte gilt. Gleichzeitig sortiert ein schwacher Haufen, der kein 100% iger Sortierbaum ist, nicht schlechter als ein gewöhnlicher Haufen und in gewisser Weise sogar noch besser. Hat die halbe Miete geschafft - mutig gehen!

Da die Wurzel des Heaps, auch eine schwache, genau das grĂ¶ĂŸte Element benötigt, tut dies die Wurzel des linken Teilbaums nicht.

Minimierung der Anzahl der Vergleiche



Ronald D. Dutton, Spezialist fĂŒr Algorithmen und Graphentheorie, stellte uns 1993 einen schwachen Haufen vor. Ein konzeptionell schwacher Stapel ist schwieriger zu verstehen (aber diese Schwierigkeit liegt eher nicht in der KomplexitĂ€t, sondern in der Extravaganz, Sie mĂŒssen Ihre Bewusstseinsmuster durch das Knie brechen) als ein gewöhnlicher Stapel, so dass er nicht viel praktische Verteilung erhalten hat. Als Dutton diese Struktur erfand, wollte er nicht nur abstrakte Abstraktionen ĂŒben, sondern verfolgte auch ein völlig pragmatisches Ziel.

Es gibt eine theoretische Untergrenze fĂŒr die SchĂ€tzung der Mindestanzahl von Vergleichen (bei den Sortierungen, bei denen diese Vergleiche weit verbreitet sind):

log n ! = n log n - n / ln 2 + O (log n), wobei 1 / ln 2 = 1,4426

Bei der Sortierung nach einem schwachen Haufen wird die Anzahl der Vergleiche minimiert und liegt nahe genug an der Untergrenze.

Dies kann von praktischer Bedeutung sein, wenn Sie Objekte anordnen mĂŒssen, deren Vergleich teuer ist, z. B. wenn lange Zeichenfolgen sortiert werden sollen.

Nachkommen jonglieren


"Links" und "Rechts" in einem schwachen Haufen ist ein situatives PhĂ€nomen. Ein Teilbaum kann entweder ein linker oder ein rechter Nachkomme fĂŒr seinen ĂŒbergeordneten Knoten sein - außerdem kann diese "links / rechts" -Relation fĂŒr den Teilbaum und den ĂŒbergeordneten Knoten wĂ€hrend des Prozesses wiederholt von einem Wert zum anderen wechseln.

FĂŒr den Elternteil anzugeben, wer seinen rechten Sohn hat und wer seine linke Tochter ist, ist nicht einfach, aber sehr einfach. Dazu benötigen Sie eine zusĂ€tzliche Bitmap (bestehend aus nur 0/1 Werten) fĂŒr die Knoten mit Nachkommen.

Erinnern Sie sich daran, wie das i- te ĂŒbergeordnete Element des Index die Indizes seines linken und rechten Nachkommen in einem herkömmlichen Stapel definiert (Indizes des Arrays gemessen von Null):

Linker Nachkomme 2 × i + 1
Rechter Nachkomme 2 × i + 2

In einem schwachen Haufen haben wir eine Kirsche auf dem Kuchen - eine Wurzel, die nur den richtigen Teilbaum hat, also werden wir diese Formeln fĂŒr die Nachkommenindizes anpassen, indem wir eine umgekehrte Verschiebung zu 1 Position hinzufĂŒgen:

Linker Nachkomme: 2 × i
Rechter Nachkomme: 2 × i + 1

Und schließlich , benötigte zusĂ€tzliche Bitmap (nenne es bIT ), wobei fĂŒr das i- te Element angegeben wurde, ob der Austausch zwischen seinen linken und rechten TeilbĂ€umen stattfindet. Wenn der Wert fĂŒr ein Element 0 ist, gab es keinen Austausch. Wenn der Wert 1 ist, gehen die linken und rechten Kinder in die entgegengesetzte Reihenfolge. In diesem Fall lauten die Formeln wie folgt:

Linker Nachkomme: 2 × i + BIT [ i ]
Rechter Nachkomme: 2 × i + 1 - BIT [ i ]

So sieht es aus. Elemente, deren Nachkommen sich "umgekehrt" befinden, werden blau hervorgehoben. Die Werte im BIT- Array fĂŒr sie sind 1.


Sie können dies ĂŒberprĂŒfen, indem Sie die ĂŒbergeordneten Werte i und die entsprechende 0/1 aus dem BIT- Array in den Nachkommenformeln einsetzen. Die Indizes der Nachkommen werden nach Bedarf angezeigt.

Wie Sie sehen können, muss die Gruppe von Elementen nirgendwo hin verschoben werden, damit ein Elternteil die linken und rechten TeilbĂ€ume im Array selbst vertauschen kann. Es wird nur der 0/1-Wert fĂŒr das ĂŒbergeordnete Element im BIT- Array umgeschaltet .

Weiter - eine magische Sitzung mit anschließender Belichtung.

Baue einen schwachen Haufen


Das Vertauschen von Nachkommen nach links und rechts ist das Hauptwerkzeug zum Konvertieren eines Datensatzes aus einem Array in einen schwachen Haufen.

Bei der Bildung des primĂ€ren schwachen Heaps mĂŒssen wir die Elemente des Arrays in umgekehrter Reihenfolge (beginnend mit dem letzten) sortieren und fĂŒr jeden von ihnen den Zweig des ersten (rechten) ĂŒbergeordneten Elements finden, fĂŒr den es der richtige Teilbaum ist.

Wenn das Element der richtige Nachkomme einer Person ist , mĂŒssen Sie nicht weit gehen. Das unmittelbare Elternteil ist das, was Sie brauchen:


Wenn das Element der linke Nachkomme einer Person ist , mĂŒssen Sie einige Stufen aufsteigen, bevor Sie den gewĂŒnschten Großelternteil treffen, fĂŒr den sich das Element im rechten Teilbaum befindet:



Dann mĂŒssen Sie den Nachkommen und den Vorfahren vergleichen, die irgendwo oben gefunden wurden. Und wenn der Nachkomme grĂ¶ĂŸer als der Vorfahr ist, muss Folgendes getan werden:

  1. Wenn der Nachkomme seine Nachkommen hat, tauschen Sie seine linken und rechten TeilbĂ€ume aus (d. H. Schalten Sie 0/1 im BIT- Array fĂŒr dieses Element).
  2. Tauschen Sie die Werte des Nachkommenknotens und des VorlÀuferknotens aus.

Schauen Sie sich ein bestimmtes Beispiel an. Nehmen wir an, die folgende Situation ist aufgetreten:


FĂŒr das Element des Arrays A [6] = 87 wurde der notwendige VorlĂ€ufer A [1] = 76 gefunden.
Der VorlÀufer A [1] ist kleiner als das Element A [6] (76 <87).
Element A [6] hat linke und rechte TeilbĂ€ume (in GrĂŒntönen markiert).
Sie mĂŒssen diese TeilbĂ€ume austauschen
( dh fĂŒr Element A [6] im BIT- Array den Wert von 0 auf 1 Ă€ndern).
Es ist auch notwendig, die Werte der Elemente A [6] und A [1] auszutauschen .

Nachdem die erforderlichen Aktionen abgeschlossen sind:


FĂŒr Element A [6] wurden die linken und rechten TeilbĂ€ume ausgetauscht
( dh im BIT- Array fĂŒr Element A [6] wurde der Wert von 0 in 1 geĂ€ndert).
Es gab auch einen Werteaustausch zwischen A [6] und A [1].

Wenn Sie das Array vom Ende bis zum Anfang durchlaufen und unterwegs dieses Verfahren fĂŒr alle Elemente ausfĂŒhren, erhalten Sie einen schwachen Haufen.

Warum dieser seltsame Mechanismus funktioniert, ist eine ErklÀrung, die nÀher am Ende des Artikels liegt.

Analyse eines schwachen Stapels


Ein Heap ist ein Heap, wenn sich das maximale Element im Stammverzeichnis befindet. Mit dieser Tatsache funktionieren alle Heap-Sortierungen auf die gleiche Weise. Die Wurzel (wo sich das Maximum befindet) tauscht Werte mit dem letzten Element des unsortierten Teils des Arrays aus. Infolgedessen nimmt der unsortierte Teil des Arrays ab und der sortierte Teil des Arrays nimmt zu. Nach diesem Austausch ist der Heap kein Heap mehr, da sich das aktuelle maximale Element nicht mehr in seiner Wurzel befindet. Der Heap muss wiederhergestellt werden, dh der resultierende Baum wird wieder zu einem Heap. Suchen Sie ein anderes maximales Element und verschieben Sie es in den Stamm.

Wir wissen, wie man einen normalen binÀren Heap wiederherstellt - mit Hilfe eines Sichters . Aber wie kann man einen schwachen Haufen wiederherstellen? Gehen Sie dazu wie folgt vor.

Von der Wurzel steigen wir die linken Nachkommen ab (bis zum niedrigsten):


Dann gehen wir die linken Nachkommen wieder hoch und auf dem Weg wird jeder linke Nachkomme mit einem Element in der Heap-Wurzel verglichen. Und wenn der nĂ€chste linke Nachkomme grĂ¶ĂŸer als die Wurzel ist, machen wir dasselbe wie in der vorherigen Stufe: Beim linken Nachkommen tauschen wir die TeilbĂ€ume (falls er einen hat) und Ă€ndern die Werte des linken Nachkommen und der Wurzel.

Infolgedessen stellen wir den schwachen Heap wieder her - das maximale Element im verbleibenden Baum wird an seiner Wurzel angezeigt.

Und wieder haben wir dieses mystische Karussell mit TeilbÀumen, die sich gegenseitig ersetzen. Was ist das Erfolgsgeheimnis? Warum erhalten wir ein sortiertes Array, wenn beim Austausch von Knoten mit Werten die linken und rechten Nachkommen des unteren Knotens vertauscht werden? Sie werden es nie erraten, obwohl die Antwort in ihrem Genie einfach ist.

Schwache Heap-Sortierung :: Schwache Heap-Sortierung


Also der endgĂŒltige Algorithmus:

  • I. :
    • I.1. -.
    • I.2. «» .
    • I.3. .
    • I.4. , :
      • I.4.. ( ⇔ ) , .
      • I.4.. «» .
  • II. , :
    • II.1. .
    • II.2. . .
    • II.3. , . :
      • II.3.. .
      • II.3.. , .
      • II.3.. , , :
        • II.3.c. 1. Wir tauschen (links ⇔ rechts) TeilbĂ€ume mit Nachkommen gegen den Knoten aus, in dem sich der aktuelle linke Nachkomme befindet.
        • II.3.c.2. Wir Ă€ndern die Heap-Wurzel und den Knoten mit dem aktuellen linken Kind.
    • II.4. An der Wurzel des schwachen Heaps befindet sich wieder das maximale Element fĂŒr den verbleibenden unsortierten Teil des Arrays. Wir kehren zu Absatz II.1 zurĂŒck und wiederholen den Vorgang, bis alle Elemente sortiert sind.


Animation (Array-Indizes in meinen Animationen beginnen mit einem):



C ++ - Code


Am Ende des Abschnitts „Links“ können sich Interessenten mit der Implementierung dieser Sortierung in C ++ vertraut machen. Hier gebe ich nur den Teil an, der den Algorithmus selbst veranschaulicht.

#define GETFLAG(r, x) ((r[(x) >> 3] >> ((x) & 7)) & 1)
#define TOGGLEFLAG(r, x) (r[(x) >> 3] ^= 1 << ((x) & 7))

void WeakHeap::WeakHeapMerge(unsigned char *r, int i, int j) {
  if (wheap[i] < wheap[j]) {//""  ?
    //  ,   
    //( "",   "")
    TOGGLEFLAG(r, j);
    //  ""  
    swap(wheap[i], wheap[j]);
  }
}

void WeakHeap::WeakHeapSort() {
  int n = Size();
  if(n > 1) {
		
    int i, j, x, y, Gparent;
    int s = (n + 7) / 8;
    unsigned char * r = new unsigned char [s];
		
    //  ,    
    // "",   ""
    for(i = 0; i < n / 8; ++i) r[i] = 0;
		
    //   
    for(i = n - 1; i > 0; --i) {
      j = i;
      //    , 
      //   ""  
      while ((j & 1) == GETFLAG(r, j >> 1)) j >>= 1;
      //       ""  
      Gparent = j >> 1;
      //  ,   
      //   ""
      WeakHeapMerge(r, Gparent, i);
    }
		
    //      -->
    //  -->    
    for(i = n - 1; i >= 2; --i) {
      //      
      //       
      swap(wheap[0], wheap[i]);
      x = 1;
      //    "" 
      while((y = 2 * x + GETFLAG(r, x)) < i) x = y;
      //  ""     
      //        
      while(x > 0) {
        WeakHeapMerge(r, 0, x);
        x >>= 1;
      }
    }
    //  -   
    //    
    swap(wheap[0], wheap[1]);
    delete[] r;
  }
}

Mir gefĂ€llt besonders, wie der BinĂ€rbaum einfach und natĂŒrlich mit bitweisen Operationen durchlaufen wird.

ZusÀtzliche SpeicherkomplexitÀt


Es scheint wie O ( n ) - ein zusĂ€tzliches Array ist erforderlich, bei dem fĂŒr Knoten mit Nachkommen (es gibt ungefĂ€hr die HĂ€lfte davon im Array) die Reihenfolge der linken / rechten TeilbĂ€ume festgelegt ist.

Es gibt jedoch eine Meinung, dass die SortierkomplexitĂ€t hier tatsĂ€chlich O (1) ist! FĂŒr ein Element benötigen wir nur ein zusĂ€tzliches Bit (Null / Eins), um die Reihenfolge der Nachkommen anzugeben. Wenn wir zum Beispiel Strings sortieren, ist es durchaus möglich, dieses zusĂ€tzliche Bit an das Element selbst anzuhĂ€ngen.

Eine andere Möglichkeit, O ( n ) in O (1) umzuwandeln, besteht darin, Flags in einer ganzen Zahl zu speichern. BinĂ€re Erweiterung von Zahlen - eine Reihe von Nullen und Einsen, die fĂŒr die Reihenfolge der TeilbĂ€ume aller Elemente des Arrays verantwortlich sind. Das i- te Element des Arrays entspricht dem i- ten Bit der Zahl.

Zeitliche KomplexitÀt


Mit der Zeit ist O ( n log n ) dasselbe wie ein regulĂ€rer Heap. Beim Sortieren von Zeilen (insbesondere langen) kann ein schwacher Heap schneller sein als ein normaler Heap. Aber das ist, wenn wir die langen Schlangen sortieren. Wenn wir die Zahlen sortieren, ist GerĂŒchten zufolge ein gewöhnlicher Haufen schneller zu verwalten.

Volles Sieben


In der Phase der Bildung des anfĂ€nglichen schwachen Haufens schlĂ€gt die ganz offensichtliche Idee in Analogie zum ĂŒblichen Haufen vor, große Elemente so hoch wie möglich anzuheben. Das heißt, wenn wir die Werte des unteren Knotens und seines Vorfahren austauschen, wĂ€re es logisch, die Schritte fĂŒr den Vorfahren sofort zu wiederholen - um seinen nĂ€chsten richtigen Vorfahren fĂŒr ihn zu finden und zu vergleichen (und wenn es auch notwendig ist, Werte + Austausch von TeilbĂ€umen auszutauschen). Und wenn möglich, heben Sie ein großes Element bis zur Wurzel an. So sieht es in der ersten Stufe aus (die Aktionen in der zweiten Stufe des Algorithmus bleiben unverĂ€ndert):


Der ZeitkomplexitÀtswert bleibt gleich.

Binomialstapel


Alles, was bis zu diesem Punkt war, ist eine TĂ€uschung, eine Illusion. NatĂŒrlich fĂŒhren wir dort formal einige Manipulationen mit dem BinĂ€rbaum durch, Ă€ndern die Knoten mit Werten, ordnen die TeilbĂ€ume neu an und so weiter. Der Algorithmus hat jedoch einen doppelten Boden, den wir nun untersuchen werden.

Um diese Art zu verstehen, mĂŒssen Sie verstehen, was ein schwacher Haufen wirklich ist.

Wenn wir ein Array nehmen, in dem die Anzahl der Elemente eine Zweierpotenz ist, dann sind der schwache Heap und der Binomialheap, die auf seiner Basis aufgebaut sind, isomorph.


Betrachten Sie nicht die Tatsache, dass ein schwacher Heap binĂ€r ist und Binomial nicht. In einem schwachen Haufen unterscheiden sich der linke und der rechte Teilbaum wesentlich. Der rechte Teilbaum ist ein Nachkomme im klassischen Sinne, der linke Teilbaum jedoch eher ein „Bruder“. Obwohl nicht. Der linke Teilbaum ist nicht einmal ein „Bruder“, sondern ein Vektor von „BrĂŒdern“ mit weniger Knoten.

Der schwache Haufen und der Binomialhaufen sind jedoch nicht zu 100% gleich, obwohl sie die engsten Verwandten sind. Der Unterschied ist offensichtlich, wenn Sie ein Array nehmen, dessen Anzahl von Elementen nicht 2 n entspricht . Die binomiale Zerlegung eines solchen Arrays ergibt eine zusammenhÀngende Liste mehrerer idealer Heaps (die Anzahl der Knoten in jedem von ihnen ist eine bestimmte Zweierpotenz):


Ein schwacher Haufen ist in diesem Fall ein unvollstÀndiger BinÀrbaum:



Der Binomialstapel und der schwache Stapel sind ZwillingsbrĂŒder. Die DNA ist dieselbe, obwohl man sie anscheinend nicht erkennen kann.

Geheimer Algorithmus


Angesichts der Tatsache, dass ein schwacher Haufen ein kryptobinomischer Haufen ist, findet das Mischen von TeilbÀumen plötzlich eine einfache ErklÀrung.


Fegen Sie mit einem schwachen Haufen das pseudobinÀre Lametta weg und betrachten Sie die tatsÀchlichen Beziehungen zwischen den Knoten im Binomialhaufenstil. Alles wird klar.

TatsÀchlich:

  1. Es gibt keine "SchwĂ€che", es ist ein vollwertiger Sortierbaum (nicht binĂ€r), in dem das Prinzip "Jeder Elternteil ist grĂ¶ĂŸer als jeder seiner Nachkommen" erreicht und beibehalten wird.
  2. In allen Phasen vergleichen wir die Nachkommen nicht mit ihren Vorfahren, sondern mit ihren unmittelbaren Eltern.
  3. Was wie ein Werteaustausch zwischen einem Nachkommen und einem Vorfahren aussieht + ein Austausch von TeilbĂ€umen in einem Nachkommen - es stellt sich heraus, dass es sich um den Austausch des VerhĂ€ltnisses selbst (Nachkomme / Elternteil) handelt. Wenn der ĂŒbergeordnete Knoten wertmĂ€ĂŸig kleiner als der Nachkomme ist, wird der ĂŒbergeordnete Knoten selbst zum Nachkommen und der Nachkomme zum ĂŒbergeordneten Knoten.

Hier ist eine ehrliche Visualisierung:



In der nÀchsten Serie


Der nĂ€chste Stapel, ĂŒber den ich sprechen möchte, ist mein Favorit - der kartesische Baum. Dies ist nicht nur ein Haufen, sondern auch ein binĂ€rer Suchbaum . Aber dann muss zuerst im nĂ€chsten Artikel etwas Interessantes ĂŒber BST-BĂ€ume geklĂ€rt werden. Und erst dann durch den Artikel und ĂŒber kartesische GesprĂ€che.

Verweise


Schwacher Heap , Binomial-Heap / Binomial-

Heap C ++ Schwache Heap-Implementierung

Ronald D. Dutton: Persönliche Seite , UCF-Website-Profil

Schwache Heaps und Freunde: Neueste Entwicklungen

Die Datenstruktur fĂŒr schwache Heaps : Varianten und Anwendungen

zur Leistung von WEAK-HEAPSORT

Adaptive Heapsort: Quellcode

Sergey Kopeliovich - Hörsaal - Schwacher Haufen (von 48:32 bis 1:16:06)

Serienartikel:




Die heutige Sortierung wird der AlgoLab-Anwendung von einem schwachen Haufen hinzugefĂŒgt, der sie verwendet. Aktualisieren Sie die Excel-Datei mit Makros.

In den Kommentaren zur Zelle mit dem Namen der Sortierung können Sie einige Einstellungen angeben. Wenn Sie siftup = 1 setzen, wird bei der Sortierung in der ersten Stufe die vollstĂ€ndige ÜberprĂŒfung verwendet (standardmĂ€ĂŸig siftup = 0).

Wenn Sie binomial = 1 vorschreiben, ist der Baum ein "binomialer Heap" (standardmĂ€ĂŸig binomial = 0, dh nur ein schwacher Heap).

More articles:


All Articles