P-6. Der ueberhaupt allerletzte Knoten ist ja der mit der Nummer heap-size(A). Einen Elternknoten bestimmt man ja jeweils durch Halbieren und Abrunden. Somit ist der Elternknoten des allerletzten Knotens [heap-size(A)/2] und das ist dann der letzte, der noch Nachfolger besitzt. Da alle spaeteren bereits trivialerweise die Heapeigenschaft erfuellen, genuegt es bei Build-Heap mit diesem Knoten zu beginnen.

P-7. Hier muss man in den Heap Paare der Form (key,object) einspeichern, wobei key eine ganze Zahl ist und object eines der Objekte, die eben in die L/F IFO Schlange hineinsollen. Man benutzt eine globale Variable act, welche anfangs auf Null gesetzt wird. DieInsert Operation haengt das Paar (key=act,object=x) in den Heap ein und zaehlt sodann act eins hoch. Zum Entfernen benutzt man im LIFO-Falle Extract-Max, im FIFO-Falle Extract-Min. Falls man Extract-Min nicht zur Verfuegung hat, kann man auch Extract-Max verwenden, muss dann aber act bei jedem Schritt dekrementieren (auf gut deutsch: eins runterzaehlen). Das Bild ist das einer KFZ Anmeldung, wo man beim Reinkommen Nummern zieht und jeweils der Kunde mit der kleinsten Nummer "dran ist"

P-8. Man vertauscht das zu loeschende Element mit dem letzten (also dem mit der Nummer heap-size(A)). Man dekrementiert sodann heap-size(A), so dass das zu loeschende Element nicht mehr gilt, und ruft anschliessend Heapify auf dem Knoten auf, in den das letzte Element gerutscht ist. Also im Prinzip genauso, wie Extract-Max.

P-9. Sei T(n) die best case Laufzeit von Quicksort auf einem Array der Groesse n. Man hat die folgende Abschaetzung von unten: T(n)>=Theta(n) + min(T(k)+T(n-k)) wobei sich das Minimum ueber alle k=1..n-1 erstreckt. Wir setzen an T(k)>=c n ln n und versuchen dies durch Induktion ueber n zu zeigen. Zunaechst mal koennen wir durch Wahl eines genuegend winzigen c erreichen, dass dies fuer alle n bis zu demjenigen n0, ab dem der Term Theta(n) groesser oder gleich d.n ist, der Fall ist. Gelte nun T(k)>=c k ln k fuer alle k<n fuer ein n>n0. Wir haben T(n) >= d n + c min f(k) nach Induktionshypothese, wobei f(k)=k ln k + (n-k)ln(n-k). Das Minimum, welches hier vorkommt koennen wir nach unten abschaetzen durch das Minimum, welches man erhaelt, wenn man k reellwertig aus [1,n-1] waehlt. Eine elementare Kurvendiskussion zeigt dann, dass das Minimum bei k=n/2 angenommen wird. (Es ist naemlich df(k)/dk=ln(k)-ln(n-k)). Wir erhalten also T(n)>=d n + cn(ln(n/2)) = dn+c n ln n - c n ln 2. Waehlt man also c<=d/ln 2, so wird T(n)>=c n ln n w.z.b.w. Wir haben hier zwei Bedingungen fuer c erhalten. Eine waehrend des Induktionsanfangs und eine eben gerade. Gluecklicherweise kann man durch genuegend kleine Wahl beide Bedingungen befriedigen, wodurch dann ein korrekter Induktionsbeweis entsteht. Natuerlich haetten wir auch gleich sagen koennen: Wir waehlen c geschickt als min(d/ln(2),min(T(k)/k(k ln k))) wobei sich das innere Minimum ueber k=0..n0 erstreckt. Dann haette man sich das mit diesen Bedingungen sparen koennen; die waeren dann naemlich aufgrund der "geschickten Wahl" von c immer wahr gewesen. Aber natuerlich kann kein Mensch solche geschickten Wahlen von alleine treffen, ohne vorher mal zu probieren, wie sich der Beweis entwickelt.

P-10. Wir setzen voraus, dass p<r. Anderenfalls wird Partition ja auch nicht aufgerufen. Wir wollen zeigen, dass dann der Aufruf Partition(A,p,r) terminiert und einen Index q aus {p..r-1} zurueckliefert, so dass gilt A[p..q]<=A[q+1..r]. Ausserdem sollten wir zeigen, dass auf A nicht ausserhalb von p..r zugegriffen wird. Wir setzen zunaechst mal die Termination voraus (partielle Korrektheit).
Wir behaupten, dass in Zeile 4 die Invariante A[p..i]<=x<=A[j..q] und i<j erfuellt ist. Zu Beginn der while Schleife ist sie erfuellt, da dann A[p..i] und A[j..q] beide leer sind. Es gilt dann nach Zeile 5 dass x<=A[j+1,q] aber A[j]<=x. Ebenso gilt nach Zeile 6, dass A[p..i-1]<=x, aber x<=A[i]. Wenn jetzt in Zeile 9 die Prozedur verlassen wird, so gilt A[p..j]<=A[j..r] wie verlangt. Anderenfalls wird in Zeile 8 die Invariante wiederhergestellt. Es bleibt zu zeigen, dass der Wert r nicht zurueckgeliefert wird. Hierzu bemerken wir, dass im ersten Durchlauf der while Schleife Zeile 6 nur einmal durchlaufen wird, da ja an der Stelle p das Pivotelement sitzt. Somit ist nach dem ersten Durchlauf der while Schleife i=p und die Schleife in Zeile 5 wird insgesamt mindestens zweimal durchlaufen.
Als letztes zeigen wir Termination und dass auf A nicht ausserhalb von p..r zugegriffen wird. Beim ersten Durchlauf der while Schleife ist klar, dass Zeilen 5 und 6 terminieren bevor j<p und i>r wird. Danach aber sind die Bereiche p..i und j..r beide nichtleer, sodass sie einen "Prellbock" fuer die beiden repeat Schleifen bilden. Im gesamten Rumpf der while Schleife gilt also p<=i,j<=r womit insbesondere die Zugriffsbedingung nachgewiesen ist. Die while Schleife schliesslich terminiert, da sich j-i bei jedem Durchlauf reduziert.