Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Entfernen eines nicht-maximalen Elements mit Kindern aus einem Heap » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Entfernen eines nicht-maximalen Elements mit Kindern aus einem Heap
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
3FingerbreitNougat
unregistriert
Entfernen eines nicht-maximalen Elements mit Kindern aus einem Heap Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von 3FingerbreitNougat: 12.07.2010 16:46.

12.07.2010 01:03
3FingerbreitNougat
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Es geht indem man das Element herausnimmt (32) und die Lücke mit dem letzten Heapelement auffüllt und die Heapeigenschaft danach wieder herstellt.

code:
1:
2:
3:
4:
5:
6:
Ursprungsheap
            50
      22        32
   18  14      1  28
11



In Arrayschreibweise:
code:
1:
2:
3:
4:
5:
| 50 | 22 | 32 | 18 | 14 | 1 | 28 | 11 | < Ursprungsheap
| 50 | 22 | 11 | 18 | 14 | 1 | 28 | __ | < 32 entfernen und  letztes Element dafür einsetzen (11)
| 50 | 22 | 28 | 18 | 14 | 1 | 11 | __ | < Heapeigenschaft wieder herstellen: 28 mit 11 tauschen


Der Heap sieht nun so aus:

code:
1:
2:
3:
4:
5:
Heap nach dem Vorgang
            50
      22        28
   18  14      1  11


MfG

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von 3FingerbreitNougat: 12.07.2010 16:46.

12.07.2010 16:45
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Entfernen eines nicht-maximalen Elements mit Kindern aus einem Heap