du hast recht. es wird negativ. das sollte man abfangen - oder hoffen, dass die versickern-methode entsprechend implementiert ist 
Geht es auch so??
for(int i = 0; i < feld.length; i++) {
tausche(feld, 0, feld.length-i);
versickern(feld, 0, i-1);
}Ist es auch korrekt?
Das tausche nur bedingt: wenn i=0 (erster schleifendurchlauf) schreibst du es an die position feld.length und bekommst eine IndexOutOfBounds-Exception ⇒ (i+1)
Das versickern ist meiner meinung nach nicht ganz richtig: du versickerst im erster durchlauf (i=0) ja eintrag 0 bis -1 (im zweiten von 0 bis 0; im dritten von 0 bis 1; d.h. du fängst vorne das zählen an). also passiert nix (oder es kommt ein fehler) obwohl der erste eintrag wahrscheinlich nicht mehr der größte ist, weil du ja getauscht hast. somit wäre die sortierung falsch.
man müsste dann noch das if einbauen (siehe oben)…
Nein, denn sonst wuerdest du beim ersten Aufruf tausche(feld, 0, feld.length) aufrufen, der letzte Index von feld ist aber feld.length - 1, da bei 0 zu zaehlen begonnen wird.
Falls tausche() und versickern() von 1 das zaehlen anfangen wuerden, dann sollte tausche(feld, 1, feld.length-i) und versickern(feld, 1, feld.length-i-1); gehen.
[Edit: Sleepy10 wieder schneller ;-)]
Danke 
Laufzeit O(n)
Im “Cormen” steht der wie man auf die Laufzeit von O(n) kommt. Ich hab das mal zusammengefasst und angefügt. Hoffe es hilft weiter!
Aber so wie ich das verstanden habe, betrifft das nur die mathematische Ebene:
"Die obere Schranke von O(n log n) ist zwar korrekt, aber nicht asymptotisch scharf. Wir können eine schärfere Schranke herleiten … ".
Attachment:
KomplexitaetHeap.pdf: https://fsi.cs.fau.de/unb-attachments/post_79751/KomplexitaetHeap.pdf
Ah cool, danke. Mir ist zwar nicht ganz klar wie das gemeint ist… so ist die Abschätzung natürlich leichter…
wahrscheinlich zu spät aber trotzdem: :-/
Ergänzungen zu den Begriffen
Heapify ist eine Unterprozedur von Build-Heap: Hier wird immer die Haldeneigenschaft auf Knotebene überprüft und hergestellt. O(h)=O(log n)
Ein n-elementiger Heap hat die Höhe h = log n.
es gibt höchstens n/2^(h+1) Knoten.
Kurze Erklärung zu der mathematischen Umformung:
∑(h/2^h) = ∑ (h(½)^h) = ½/(1-½)^2=2
der Teil ganz rechts von “=” kommt von der allgemeinen Form ∑ (k x^k) = x/(1-x)^2;
∑ (h(½)^h) : hier wird x=½ quasi schon vorgegeben, h≙k und dann eben einfach ½ in den Rest einsetzen
⇒ ½/(1-½)^2 = 2