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
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
