D a t e n s t r u k t u r    H e a p

HMO,   Warendorf,   Januar 1998



Aufgabe d)
Wieviel Schichten hat ein Heap mit 6, 7, 8, 9, 1023, 1024, 4000, 4095, 4096, n Elementen ?


Aufgabe e)
Wieviel Elemente hat ein Heap mindestens und höchstens, wenn er 2, 3, 4, 10, 11, n Schichten hat ?


Behauptung 1:  Sn sei die Anzahl der Elemente in der n-ten Schicht eines vollständigen Binärbaums. Es gilt: Sn = 2n-1 .

Beweis durch vollst. Induktion:

    I     n=1:    S1 = 1 = 21-1 = 20

    II   n auf n+1:  Die n+1-te Schicht hat doppelt soviel Elemente wie die n-te Schicht, weil jedes
         Vorgängerelement in der n-ten Schicht genau 2 Nachfolger in der n+1-ten Schicht haben muß, damit der
         Binärbaum vollständig wird; also:   Sn+1 = 2*Sn = 2*2n-1 = 2n  qed.


Behauptung 2:  An sei die Anzahl der Elemente in einem vollständigen Binärbaum mit n Schichten. Es gilt: An = 2n-1 .

Beweis durch vollst. Induktion:

    I     n=1:    A1 = 1 = 21-1 = 2-1

    II   n auf n+1:  Zur Anzahl An kommt noch die n+1-te Schicht hinzu, deren Anzahl der Elemente
         in Behauptung 1 als 2n bestimmt wurde.
         Also:   An+1 = An + Sn+1 = 2n-1 + 2n = 2*2n-1 = 2n+1-1  qed.


Die jetzt bewiesene Behauptung 2 liefert die allgemeine Antwort zur Aufgabe e und in Kenntnis der Tatsache, daß der Logarithmus die Umkehrung zur Exponentiation ist, auch die Antwort auf Aufgabe d.


Elemente:678910231024400040954096n
Schichten:33441011121213[log2n]+1


Schichten:2341011n
Elemente:2 .. 34 .. 78 .. 15512 .. 10231024 .. 20472n-1 .. 2n-1




HTML-Texte: ADT Heap HAUPTTEXT

zur Informatik-Leitseite


© HMO, Neubearbeitung Januar 1998