Entfernen eines nicht-maximalen Elements mit Kindern aus einem Heap |
12.07.2010, 01:03 | Auf diesen Beitrag antworten » | |||||||||||||||
3FingerbreitNougat | Entfernen eines nicht-maximalen Elements mit Kindern aus einem Heap Man hat einen Heap gegeben (in Standartnotation): Wert: 50 22 32 18 14 1 28 11 Index: 0...1...2...3...4.5..6...7 Jetzt sollen wir das Element mit dem Wer 32 entfernen. Ich hab keine Ahnung wie das geht. Das entfernen des Elements mit dem maximalen Wert (50) ist easy. k-tes Element einfügen und dann rekursiv Heapkriterium (Vaterknoten >= Kinderknoten) reparieren. Wie geht es jetzt aber wenn man ein Element in der Mitte mit Kindern entfernt? MfG |
|||||||||||||||
|
||||||||||||||||
12.07.2010, 16:45 | Auf diesen Beitrag antworten » | |||||||||||||||
3FingerbreitNougat | Es geht indem man das Element herausnimmt (32) und die Lücke mit dem letzten Heapelement auffüllt und die Heapeigenschaft danach wieder herstellt.
In Arrayschreibweise:
Der Heap sieht nun so aus:
MfG |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|