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 » Antwort erstellen » Hallo Gast [Anmelden|Registrieren]

Antwort erstellen
Benutzername: (du bist nicht eingeloggt!)
Thema:
Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33
smileWinkDaumen hoch
verwirrtAugenzwinkerngeschockt
Mit ZungeGottunglücklich
Forum Kloppebösegroßes Grinsen
TanzentraurigProst
TeufelSpamWillkommen
LehrerLOL HammerZunge raus
Hilfe 
aktuellen Tag schließen
alle Tags schließen
fettgedruckter Textkursiver Textunterstrichener Text zentrierter Text Hyperlink einfügenE-Mail-Adresse einfügenBild einfügen Zitat einfügenListe erstellen CODE einfügenPHP CODE farbig hervorheben
Spamschutz:
Text aus Bild eingeben
Spamschutz

Die letzten 2 Beiträge
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.

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