Hallo!

Ich habe mich mit dem Thema Halden (Heap) auseinander gesetzt und es gibt ja zwei verschiedene Varianten. Die Min- und die Max-Halde. Da man die Halde für den Heap-Sort-Algorithmus braucht, bestimmt doch die Variante der Halde, in welcher "Richtung" man das Array später sortieren kann oder?

Es wäre beispielsweise wenig sinnvoll eine Min-Halde zu erzeugen, wenn man das Array, das sie enthält, später absteigend sortieren will?!

mfg
Syrill

Vielleicht verstehe ich deine frage Stellung nicht,

aber der Heap-Sort-Algorithmus Sortiert die Werte doch nur innerhalb des Array um. Dabei nimmt er immer nur einen Wert von seiner Position in einem Externen Speicher (Heap) und verschiebt einen Zweiten Wert von seiner Array Position auf die gerade frei gewordene stelle und fügt den ersten an die nun frei gewordene stelle.


Die Richtung ssollte immer egal! sein.

Also nach meinem Verständnis sollte ein Min Heap reichen.

Der Heap ist doch selbst wiederrum auch nur ein Array? Und wenn genau dieses Array umsortiert werden soll, dann weiß ich da persönlich nicht weiter. Zumindest nicht, wenn man versucht es inplace zu machen.

Also Lesen bildet und nach dem ich das getan habe

Also welchen Heap du erzeugst hängt ausschließlich von der Sortier-Richtung ab, Min Heap und MaxHeap (nach dem was ich eben gelesen habe) Unterscheiden sie nur die reihen folge der werte die in den heap gelegt werden.

Eine Absteigende Sortierung ist immer Max-Heap

Eine Aufsteigene Sortierung ist Min Heap

Zumindest nach dem was ich eben nach gelesen habe.

Deine Halde die du erzeugst muss auch in der Lage sein deine Werte aufzunehmen, was für ein Typ das nun ist ist abhängig davon was du damit vorhast.


Erweiterung: ich habe ein Beispiel anhand eines Baumes - Max Heap hat als Baum root den Größten wert des Heaps, während ein Min Heap den kleinsten Wert als Root hat.

Das Problem ist dabei folgendes:
Ich habe eine Aufgabenstellung, nach der ich versuche vorzugehen. In dieser Aufgabenstellung muss ich zuerst ein Min-Heap erstellen. Das mache ich und er ist korrekt so. Im Anschluss aber soll ich das Array, das diesen Heap speichert inplace, mit Hilfe von Heap-Sort umsortieren, so dass es absteigend sortiert ist.

• Problem #1: Bei Heap-Sort "lösche" ich nach dem auslesen des jeweils nächsten Elements dieses immer, damit der Heap neu "aufrücken" kann und ich wiederrum....
  Aber wenn das würde in meinem Fall heißen, dass ich Elemente aus dem zu sortierendem Array lösche?!
• Problem #2: Wie nutze ich Heap-Sort, um einen Min-Heap absteigend zu sortieren?!

Ausgangslage: Du hast ein Unsortiertes Array welsches mittels Heapshort sortiert werden soll.

Schritt 1: je nach art (Absteigend oder Aufsteigen) legst du einen Heap an (Min Heap und Max heap haben haben die selbe größe, einziger unterschied ist die reihen folge der daten die dort rein kommen)

Schritt 2: du Überführst dein Array in den Heap (einen Wert aus Array in den Heap schreiben und aus den Array Löschen, wobei der wert denn du in den heap schreibst den regeln des heaps entsprechen muss)

Schritt 3: du nimmst den ersten wert aus dem heap und schreibst in dein nun leeres array
im Min Heap ist der kleinste wert immer an erster stelle des heaps
beim Max Heap ist der Größte wert immer an der ersten stellen
nimmst du den ersten wert raus ist das nicht mehr gegeben und der Heap muss erneut umgeordnet werden

Schritt 4: du sortierst dein heap erneut damit er den heap regeln entspricht

Schritt 5: du wiederholst solange schritt 3 und 4 bis dein heap leer ist und du zu Schritt 6 übergehst.

Schritt 6: Dein Heap ist Leer alle wert stehen nun wieder im Array welches nun sortiert ist.



beim internen sortieren machst du ein Feld frei der wert der dort steht wird in einem Dummy wert zwischen gespeichert. Anschließen verrückst du einen anderen wert in dem du seinen wert von Position y auf x Verschiebst

Code :

1	array[x] = array[y];

anschließend kommt dein wert aus dem Dummy in array[y];


--Hier ein Link-- der WikiPedia artikel Visualisiert das Verfahren recht gut.

Es ist sehr nett von dir, dass du mir HeapSort so ausführlich erklärst , aber ich verstehe HeapSort durchaus und kann es auch umsetzten.
Das Problem im aktuellen Fall ist eben, dass:

1. das zu sortierende Array das gleiche ist, wie das Array, das den Heap speichert.
2. ich es mit einem Min-Heap zu tun habe, später aber ein absteigendes Array haben soll.

Jetzt kommen wir der sache endlich näher

1. sollte kein Problem sein weil wie ich bereits beschrieben habe das du ein Dummy Speicher benötigst welcher Einen einzigen Wert aufnehmen muss. Sortieren ohne einen wert wo anders zwischen zu lagern ist gar nicht möglich. Und kein Verfahren bzw dessen Umsetzung sieht keinen Zwischen lagern einzelner werte/Objekte vor

angenommen du bis an stelle array[x] du willst den wert von array[f] nach x rüber haben, dann nimmst du array[x] in den dummy machst array[x] = array[f] und anschließen array[f] = dummy. Schon hast du inplace werte getauscht.

Alleine für das raus schreiben vom Heap bereich würde es ungefähr so aussehen

Code :

1 2 3 4 5 6 7 8 9 10

for(int i = array.lenght - 1; i <= 0; i-- ){      dummy = array[0];      array[0] = array[i];      array[i] = dummy;        array = short_array_Zwischen_0_Und_i_(array, i);// <-- Hierbei sollte der der bereich                                               //ab i nicht mehr verändert werden   }

der Code ist nur geschmiert sollte aber deutlich machen wie du ungefähr vorgehen musst.


Zu 2: Und Min Heap bedeutet nur das das die Art und weiße wie deine werte verglichen und sortiert werden ein bestimmte ist.
Natürlich es mit einem Min Heap ist möglich.

Beispiel

Beispiel Array felder --> 5,4,8,7,3,9,2,1

dein heap beginnt mit --> 1

An der Spitze des Min Heaps steht der Kleinste wert, an welche stelle in das sortierte Array schreibst ist deine sache es muss nur das raus kommen was du willst.

Absteigend deute ich so 9,8,7,6,5,4,3,2,1
Wenn mit Absteigend das gemeint ist wie ich es verstehe nimmst du die spitze des Heap in deinen dummy Speicher (also beim ersten mal die 1) und schreibst den Letzten wert des Arrays (Heaps) an die stelle wo die spitze des Heaps war und den wert welcher die Heap spitze war aus dem dummy an die nun freie stelle

Also dein Array [ <Dein Heap größe 9 stellen> ]
Also dein Array [ <Dein Heap größe 8 stellen> ,1 ]
Also dein Array [ <Dein Heap größe 7 stellen> ,2,1 ]
Also dein Array [ <Dein Heap größe 6 stellen> ,3,2,,1 ]
Also dein Array [ <Dein Heap größe 5 stellen> ,4,3,2,1 ]
Also dein Array [ <Dein Heap größe 4 stellen> ,5,4,3,2,1 ]
Also dein Array [ <Dein Heap größe 3 stellen> ,6,5,4,3,2,1 ]
Also dein Array [ <Dein Heap größe 2 stellen> ,7,6,5,4,3,2,1 ]
Also dein Array [ <Dein Heap größe 1 stellen> ,8,7,6,5,4,3,2,1 ]
Also dein Array [ <Dein Heap größe 0 stellen> ,9,8,7,6,5,4,3,2,1 ]

Wenn du die Sortier richtung wechseln willst bleiben zwei möglichkeiten

1. Anstellen Min Heap MAx Heap nutzen.

2. richtung aus der du vom heap ins array schreibst ändern


Also dein Array [ 1, <Dein Heap größe 8 stellen> ]
Also dein Array [ 1,2,3,4,5, <Dein Heap größe 4 stellen> ]
Also dein Array [ 1,2,3,4,5,6,7,8,9, <Dein Heap größe 0 stellen> ]