Heap-Sort

valentina2013

Bekanntes Mitglied
so, ich schon wieder :)

hier die Aufgabenstellung:

Sie haben einen Max-Heap im Rahmen des Sortierverfahrens Heapsort kennengelernt. Maßgeblich war dabei die Erkenntnis, dass man trotz ihrer zweidimensionalen Darstellung vollständige Binärbäume mit N Knoten in eindimensionalen Arrays der Länge N speichern kann. Nummeriert man die Knoten eines Heaps ausgehend von der Wurzel fortlaufend durch, sodass man der Wurzel den Index 0 zuweist, dann kann man für jeden Elternknoten i den Index des linken und rechten Kindes (sofern es denn existiert) mithilfe der folgenden Vorschrift berechnen:
linkesKind(i)=2*i+1 bzw. rechtesKind(i)=2*i+2.
Wir wissen bereits, dass man aus einem Max-Heap das Element mit der höchsten Priorität in logarithmischer Zeit entfernen kann – aber wie sieht das Einfügen neuer Prozesse aus? Da wir beim Einfügen von neuen Knoten in den Heap ständig das Array verlängern müssten, einigen wir uns auf eine hinreichend große Maximalkapazität
N<=K und legen dementsprechend ein Array der Länge K an. Beim Einfügen wird dann einfach die Variable N inkrementiert. Die Einfügeoperation läuft dann wie folgt ab:
a).
Schreibe die neue Priorität an die Stelle N des Arrays. Inkrementiere die Anzahl N um eins.
b).
Korrigiere die eventuell verletzte Heap-Eigenschaft mithilfe sukzessiver Vergleiche mit den
Elternknoten, bis man an der Wurzel angekommen ist.

was ich bis jetzt gemacht habe: ich erstelle eine Array mit der Länge K, fülle dei mit Zahlen und sortiere die mit Heap-sort. Eigentliches Problem ist das Einfügen von neuen Knoten, ich sollte es so oft machen bis N<=K, und jedes Mal überprüfen ob Heap-Eigenschaft noch besteht und wenn nicht dann Korregieren. Wie kann ich das Einfügen machen ohne While Schleife? Habt ihr einen besseren Ansatz zu der Aufgabe?

danke sehr :)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
V Ist Off-Heap-Speicher dasselbe wie Stack-Speicher? Java Basics - Anfänger-Themen 2
S Java Client-je nach Heap Size Größe startet Applikation oder nicht Java Basics - Anfänger-Themen 4
KogoroMori21 Stack und Heap Speicher Java Basics - Anfänger-Themen 1
G Min und Max heap Java Basics - Anfänger-Themen 1
M Java heap space Fehlermeldung beheben Java Basics - Anfänger-Themen 3
F speicherort stack oder heap Java Basics - Anfänger-Themen 1
M Algorithmus Max-Heap? Java Basics - Anfänger-Themen 3
P Stack, Heap Java Basics - Anfänger-Themen 13
G Heap Space erhöhen (64bit) Java Basics - Anfänger-Themen 45
S Java memory fehler: Exception in thread "AWT-EventQueue-0" java.lang.OutOfMemoryError: Java heap spa Java Basics - Anfänger-Themen 5
A Heap Space Error bei rekursiver Suche in Dateien trotz nur einer Zeile im Speicher Java Basics - Anfänger-Themen 26
J Array von Objekten, wie schauts im Heap / Stack aus ? Java Basics - Anfänger-Themen 7
M Frage zu Stack und Heap Java Basics - Anfänger-Themen 1
H Heap-Auslasung verdoppelt sich schlagartig Java Basics - Anfänger-Themen 3
M Java Arbeitsspeicherverbrauch, Heap Space error korrigieren? Java Basics - Anfänger-Themen 18
H Heap Java Basics - Anfänger-Themen 4
D Java Heap Space Probleme Java Basics - Anfänger-Themen 7
B Stack/Heap Frage Java Basics - Anfänger-Themen 36
C Warning: Type safety: Potential heap pollution via varargs parameter array Java Basics - Anfänger-Themen 5
S Input/Output Java heap space Java Basics - Anfänger-Themen 8
W Compiler-Fehler "Could not reserve enough space for object heap"... und dann raucht das Programm ab Java Basics - Anfänger-Themen 3
B OOP Zwei gleichnamige Objekte auf dem heap Java Basics - Anfänger-Themen 4
H Heap Java Basics - Anfänger-Themen 2
A Java heap space Java Basics - Anfänger-Themen 11
T Out of Memory (Java Heap Space) Java Basics - Anfänger-Themen 9
B Heap-Speicher wieder freigeben Java Basics - Anfänger-Themen 10
D java heap space Java Basics - Anfänger-Themen 6
S Java Heap space trotz -Xmx1024 Java Basics - Anfänger-Themen 10
N Heap Dump Java Basics - Anfänger-Themen 23
C 'OutOfMemoryError: Java heap space' Java Basics - Anfänger-Themen 5
E ternärer Heap in Array-Form Java Basics - Anfänger-Themen 6
L heap space, LinkedList umspeichern Java Basics - Anfänger-Themen 15
E begrenzung des platzes im heap Java Basics - Anfänger-Themen 4
D java.lang.outofmemoryerror java heap space bei Hashtable Java Basics - Anfänger-Themen 3
G Frage zur Heap-Belegung Java Basics - Anfänger-Themen 2
neurox java.lang.OutOfMemoryError: Java heap space Java Basics - Anfänger-Themen 18
B java.lang.OutOfMemoryError: Java heap space bei Musikplayer Java Basics - Anfänger-Themen 7
M Java Heap Space durch Übergang von einer Klasse in die ander Java Basics - Anfänger-Themen 3
N Applet Heap vergrößern Java Basics - Anfänger-Themen 10
G warum heap space problem? Java Basics - Anfänger-Themen 6
G heap size vergrößern Java Basics - Anfänger-Themen 6
S memory heap problem Java Basics - Anfänger-Themen 9
V warum heap space überlastung Java Basics - Anfänger-Themen 2
G error wegen heap space Java Basics - Anfänger-Themen 4
M Beadarf ermitteln für Java heap space Java Basics - Anfänger-Themen 4
M Dateien lesen/schreiben und Heap Space Probleme Java Basics - Anfänger-Themen 8
G Aktuelle Heap-Größe auslesen? Java Basics - Anfänger-Themen 3
G Aus Array einen Heap erstellen Java Basics - Anfänger-Themen 5
D suchbaum out of heap space Java Basics - Anfänger-Themen 8
D Heap erweitern Java Basics - Anfänger-Themen 3
R Java heap space Java Basics - Anfänger-Themen 4
E Heap Size einstellen Java Basics - Anfänger-Themen 7
S OutOfMemoryError: Java heap space Java Basics - Anfänger-Themen 6
J Morgen Java-Klausur. Stack, Heap, Method-Area Java Basics - Anfänger-Themen 2
M Java Heap Space während der Laufzeit ändern Java Basics - Anfänger-Themen 2
E fehlermeldung "java heap space" Java Basics - Anfänger-Themen 21
E wieviele objekte am heap?? Java Basics - Anfänger-Themen 14
emreiu Formatiertes Output bei Insertion Sort Java Basics - Anfänger-Themen 6
O Sortieren mit Insertion Sort Java Basics - Anfänger-Themen 3
Tw1Z Erste Schritte Sort in java Java Basics - Anfänger-Themen 2
M Bubble Sort - Int[] Array sortieren Java Basics - Anfänger-Themen 2
X Collections.sort als Lambda Java Basics - Anfänger-Themen 14
berserkerdq2 Geht collections.sort bei allen? Linkedhashset, ArrayList, HashSet etc. Java Basics - Anfänger-Themen 4
L Insertion Sort bei zweidimensionalem Array Java Basics - Anfänger-Themen 7
KogoroMori21 Textdatei einlesen im Array (Selection Sort Algorithmus) Java Basics - Anfänger-Themen 3
Marc111111111 Selection Sort in Java?? Java Basics - Anfänger-Themen 6
G Insertion Sort mit Aray Java Basics - Anfänger-Themen 5
O Collections.sort und List.sort mit Lambda Verwirrung Java Basics - Anfänger-Themen 5
B Collections.sort mit zwei Bedingungen? Java Basics - Anfänger-Themen 4
M Collection.sort sortiert nicht Java Basics - Anfänger-Themen 7
CptK Best Practice Merge-Sort als Baum darstellen Java Basics - Anfänger-Themen 3
P Java Bubble Sort,Anfängerfehler Java Basics - Anfänger-Themen 4
S Methoden Sort Array Java Basics - Anfänger-Themen 9
I Erste Schritte sort() vs. sort() Java Basics - Anfänger-Themen 9
BadBat ArrayList<String> sort by last word Java Basics - Anfänger-Themen 8
U Methoden Zweidimensionales Array mit Arrays.sort sortieren? Java Basics - Anfänger-Themen 22
X Quick Sort - Vergleichsoperationen zählen Java Basics - Anfänger-Themen 0
O Insertion Sort Java Basics - Anfänger-Themen 4
N Bubble Sort sortieren mit Int Werte Java Basics - Anfänger-Themen 8
C OOP array Sortieren ohne den sort Befehl Java Basics - Anfänger-Themen 10
S int-Array mittels Arrays.sort() in einer Schleife sortieren. Java Basics - Anfänger-Themen 2
N Schlüsselworte Bubble Sort nach eigener Ordnung Java Basics - Anfänger-Themen 8
J Fehler im Selection Sort Java Basics - Anfänger-Themen 5
O Listen sort-Methode Java Basics - Anfänger-Themen 1
M Quick Sort Java Basics - Anfänger-Themen 4
M Methoden Quick Sort Java Basics - Anfänger-Themen 5
T array.sort mit zwei Kriterien Java Basics - Anfänger-Themen 8
S Liste und Bubble Sort Java Basics - Anfänger-Themen 4
H Collections Was ist schneller - HashMap + Sort v TreeMap? Java Basics - Anfänger-Themen 75
S Fehler bei Arrays.sort(array) - Methode!? Java Basics - Anfänger-Themen 3
P collections.sort Java Basics - Anfänger-Themen 2
B Arrays.sort Java Basics - Anfänger-Themen 4
P schneller Sort ? Java Basics - Anfänger-Themen 2
S Bubble Sort Java Basics - Anfänger-Themen 5
B Merge-Sort Analyse Java Basics - Anfänger-Themen 27
K Array.sort() Java Basics - Anfänger-Themen 12
H Etwas wie sort() / sorted() in JAVA-Collections? Java Basics - Anfänger-Themen 5
B 2 dimensionales Array: Selection Sort Java Basics - Anfänger-Themen 4
F Methoden Insert Sort Fehler Java Basics - Anfänger-Themen 10
P Ein sort problem Java Basics - Anfänger-Themen 6

Ähnliche Java Themen

Neue Themen


Oben