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:  S_n sei die Anzahl der Elemente in der n-ten Schicht eines vollständigen Binärbaums. Es gilt: S_n = 2^n-1 .

Beweis durch vollst. Induktion:

    I     n=1:    S₁ = 1 = 2^1-1 = 2⁰

    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:   S_n+1 = 2*S_n = 2*2^n-1 = 2ⁿ  qed.

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

Beweis durch vollst. Induktion:

    I     n=1:    A₁ = 1 = 2¹-1 = 2-1

    II   n auf n+1:  Zur Anzahl A_n kommt noch die n+1-te Schicht hinzu, deren Anzahl der Elemente
         in Behauptung 1 als 2ⁿ bestimmt wurde.
         Also:   A_n+1 = A_n + S_n+1 = 2ⁿ-1 + 2ⁿ = 2*2ⁿ-1 = 2ⁿ⁺¹-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.