Frage zum HEAP

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Frage zum HEAP
Hallo!

Ich mache gerade das Übungsblatt 7 durch, und dabei ist mir etwas aufgefallen:
Die Defitinitionen des Heaps unterscheiden sich in der Vorlesung und in der Übung :-/

Vorlesung 6.2. (+ 2 Algobücher, in denen ich nachgeschaut habe):
Ein Binärbaum B heißt Halde/Heap wenn,

  • B ein vollständiger Baum ist
  • Der Schlüssel eines jeden Knotens KLEINER oder gleich als die Schlüssel seiner Kinder ist.
    Beispiel:
                         1
                3                 2
            5       9        8       11     

7. Übung Aufgabe 13
Ein binärer Baum ist ein Heap, wenn die Schlüssel jeden Knotens mindestens so groß sind wie die Schlüssel seiner beiden Kinder.
Beispiel:

                         8
                6                 7
            3       4        5       2     

Die Definition in der Übung ist also genau das Gegenteil wie von der Definition in der Vorlesung, bzw. in meinen Büchern!
Deshalb die Frage: WARUM? :rolleyes:


Soweit ich das in Erinnerung habe steht in der Übung extra dabei, dass man die Heap Eigenschaft in diesem Fall extra andersrum definiert.


ja ich glaub auch sowas mal gehört zu haben…


Dem Heap ist es im Im Prizip egal welche Ordnungsrelation du verwendest, Hauptsache die ist total.

Ob du >= oder <= verwendest ist dann egal, bzw von der Aufgabenstellung abhängig.


OK Danke.

Dachte bisher immer Heap sei fest mit “Knoten<=Kinder” definiert. Wieder was dazugelernt :smiley:

Das die den Heap bei der Übung bewusst andersrum definiert haben, habe ich wohl nicht mitbekommen :zzz: .