Heap Sort < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Wie funktioniert der Heap Sort? |
Ich habe irgendwie unterschiedliche Lösungen dazu gefunden.
Bei den einen ist die Wurzel immer jeweils die größte Zahl und wird dann ausgegeben, bei anderen Quellen ist es die kleinste Zahl die am Ende ausgegeben wird.
Was stimmt?
Oder gibt es beide Varianten?
Fest steht - Heap Sort funktioniert folgendermaßen:
1.) Wurzel als kleinstes/größtes???? Element ausgeben.
2.) letztes Blatt (unten rechts) zur Wurzel machen, Blatt streichen
3.) Ist ein Knoten größer/kleiner??? als einer seiner Nachfolger, so diesen mit dem kleiner/größeren der Beiden NAchfolger tauschen.
4.) Ist gemäß 3 kein Tausch mehr möglich, so liegt wieder ein Heap vor - mt diesem wird genauso verfahren, solange bis der Baum abgearbeitet ist.
Stimmt das?
Danke!!!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:18 Do 17.09.2009 | | Autor: | felixf |
Hallo!
> Wie funktioniert der Heap Sort?
> Ich habe irgendwie unterschiedliche Lösungen dazu
> gefunden.
> Bei den einen ist die Wurzel immer jeweils die größte
> Zahl und wird dann ausgegeben, bei anderen Quellen ist es
> die kleinste Zahl die am Ende ausgegeben wird.
> Was stimmt?
> Oder gibt es beide Varianten?
Nun, das einzige was du brauchst ist eine Menge $M$ und eine (totale) Ordnung [mm] $\le$ [/mm] auf $M$. Ob du nun $M = [mm] \IZ$ [/mm] und [mm] $\le$ [/mm] als die normale Ordnung nimmst, oder [mm] $\le$ [/mm] als die umgekehrte Ordnung, macht keinen Unterschied.
Ob du das Ergebnis dann "verschiedene Varianten" nennen willst oder einfach "Spezialfall von einer allgemein formulierten Version des Heapsorts" (mit abstrakter Menge $M$ und abstrakter Ordnung [mm] $\le$ [/mm] auf dieser Menge) ist doch voellig egal.
> Fest steht - Heap Sort funktioniert folgendermaßen:
> 1.) Wurzel als kleinstes/größtes???? Element ausgeben.
> 2.) letztes Blatt (unten rechts) zur Wurzel machen, Blatt
> streichen
> 3.) Ist ein Knoten größer/kleiner??? als einer seiner
> Nachfolger, so diesen mit dem kleiner/größeren der Beiden
> NAchfolger tauschen.
> 4.) Ist gemäß 3 kein Tausch mehr möglich, so liegt
> wieder ein Heap vor - mt diesem wird genauso verfahren,
> solange bis der Baum abgearbeitet ist.
>
>
> Stimmt das?
Ja.
LG Felix
|
|
|
|
