Warum ist Heapsort nicht stabil?

Ich versuche zu verstehen, warum heapsort ist nicht stabil.
Ich habe gegoogelt, aber habe nicht gefunden eine gute, intuitive Erklärung.

Verstehe ich die Bedeutung von stabilen Sortieren - es erlaubt uns zu Sortieren, basierend auf mehr als einen Schlüssel, die kann sehr nützlich sein (D. H., mehrere Sortierungen, die jeweils basierend auf einer anderen Taste. Da jede Art unter Beibehaltung der relativen Ordnung der Elemente, Vorherige Sortierungen können bis zu geben, eine endgültige Liste von Elementen sortiert nach mehreren Kriterien).
Jedoch, warum würden Sie nicht heapsort erhalten diese als gut?

Vielen Dank für Ihre Hilfe!

InformationsquelleAutor der Frage JMS | 2013-10-12

  1. 20

    Die endgültige Sequenz der Ergebnisse von heapsort kommt von entfernen von Elementen aus dem heap erstellt in rein Größe, um (basierend auf dem Schlüssel-Feld).

    Alle Informationen über die Reihenfolge der Elemente in der original-Reihenfolge wurde verloren, während der heap creation Phase, welche kam zuerst.

    InformationsquelleAutor der Antwort Baldrick

  2. 25

    Heap-sort instabilen Beispiel

    Berücksichtigen array 21 20a 20b 12 11 8 7 (schon in max-heap-format)

    hier 20a = 20b nur zur Unterscheidung der Bestellung stellen wir Ihnen als 20a und 20b

    Während heapsort ersten 21 entfernt und gelegt in den letzten index dann 20a entfernt platziert und in der letzten, aber einem index und 20b im letzten aber zwei index-also nach heap sort das array sieht aus wie

    7 8 11 12 20b 20a 21.

    Bewahrt jedoch nicht die Reihenfolge der Elemente und damit nicht stabil

    InformationsquelleAutor der Antwort KD157

  3. 18

    Stabil bedeutet, wenn die zwei Elemente haben den gleichen Schlüssel, Sie bleiben in der gleichen Reihenfolge oder Positionen. Aber das ist nicht der Fall für Heap-Sortieren.

    Heapsort ist nicht stabil, weil die Operationen auf dem heap ändern kann die relative Reihenfolge gleicher Elemente.

    Vom hier:

    Beim Sortieren (in aufsteigender Reihenfolge) heapsort ersten peaks die größte
    element und legen Sie es in den letzten von der Liste. So, das element,
    wurde zuerst ausgewählt, bleibt die Letzte und das element, das ausgewählt worden
    Sekunde bleibt, um das Letzte element in der sortierten Liste.

    Wieder, Build-Max-Heap-Verfahren funktioniert so, dass es beibehalten der Reihenfolge
    der gleiche Wert (ex:3a,3b) in den Aufbau der heap-Struktur. Für die Extraktion
    die maximale element, es funktioniert auch aus der Wurzel und versuchen, zu bewahren
    die Struktur des Baumes (mit Ausnahme der änderung für Heapify).

    Also, was passiert, für die Elemente mit dem gleichen Wert [3a,3b] heapsort-picks
    3a vor der 3b, aber bringt 3a rechts der 3b. So, die Liste ist
    sortiert in aufsteigender Reihenfolge erhalten wir die 3b vor der 3a in der Liste .

    Wenn Sie versuchen, heapsort mit (3a,3b,3b), dann können Sie visualisieren den
    situation.

    InformationsquelleAutor der Antwort Rahul Tripathi

  4. 1

    Angenommen, eine Matrix der Größe n (willkürlicher Wert) und wenn gibt es zwei aufeinander folgende Elemente(angenommen 15) im heap, und wenn Ihre Eltern Indizes haben Werte wie 4 und 20.(dies ist die tatsächliche Reihenfolge (....4,20 ,.....,15,15.....). die relative Reihenfolge von 4 und 1. 15 bleibt aber gleich 20>15,2. 15 kommt nach vorne(swap), wie definiert in den heap-sort-Algorithmus, die relative Reihenfolge ist Weg.

    InformationsquelleAutor der Antwort Karthik Priyatham

  5. 0

    Ich weiß, das ist eine späte Antwort, aber ich will hinzufügen, meine 2 cents hier.
    Betrachten wir ein einfaches array mit 3 Integer-zahlen. 2,2,2 wenn man nun die build-max-heap build-max-heap-Funktion, werden Sie feststellen, dass die array-Speicherung der Eingang hat sich nicht geändert, wie es bereits in Max-heap-form. Nun, wenn wir die Wurzel des Baums am Ende der Reihe in der ersten iteration die heap-sort die Stabilität der array ist schon Weg. So dort haben Sie ein einfaches Beispiel für die Instabilität von heap-sort.

    InformationsquelleAutor der Antwort dipen bhatt

Schreibe einen Kommentar