Algorithmus: Schlüssel eines Datensatzes im Heap ändern

[Cherrycoke]

Aufgabe:

In einem Heap mit n Datensätzen werde der Schlüssel eines beliebigen Datensatzes geändert.

Formulieren Sie einen Algorithmus mit Aufwand O(log(n)), der die Heapstruktur wieder herstellt. (Sie müssen also auch eine Aufwandsanalyse durchführen!)

Lösung:

[U]Algorithmus[/U]: Heap bearbeiten

[U]Eingabe[/U]: Zu bearbeitende Heap h, Schlüssel s des zu bearbeitenden Knotens,  neuer Schlüssel t

[U]Ausgabe[/U]: Heap h

Suche Knoten n mit Schlüssel s;

Wenn Knoten n mit Schlüssel s gefunden:

Ersetze s durch t

Sonst:

	Gebe aus „Zu bearbeitender Schlüssel nicht gefunden“;

	Beende den Algorithmus;

Solange t kleiner als Schlüssel eines Sohnes von n

	Bestimme den größeren Schlüssel g der beiden Söhne von n;

	Vertausche n mit dem Sohn mit g (sift down);	

Solange t größer ist als Schlüssel des Vaters

	Vertausche t mir seinem Vater (sift up);

Meine erste Frage wäre, ob der Algorithmus so korrekt ist, oder ob ich etwas vergessen habe zu ebachten?

Meine zweite Frage wäre, wie ich die Aufwandsanalyse durchzuführen habe. Darin bin ich leider nicht so fit.

O(log(n)) im Worstcase ist meiner Meinung nach gegeben, da ich maximal h (Höhe) Schritte durchführen kann, indem ich entweder die kleinste Zahl ganz oben einfüge, oder die größte Zahl ganz unten. Die Höhe ist ja gleich log(n). Aber wie schreibe ich das nun mathematisch korrekt auf?

[lupo49]

..Edit (hab an Hashmap gedacht).

[flashpixx]

Aber wie schreibe ich das nun mathematisch korrekt auf?

Induktionsbeweis über N

[lupo49]

Wie fängt man denn sinnvoll an, um die entsprechende Bestandteile des Induktionsbeweises aufzubauen?

[flashpixx]

Den Algorithmus einmal als Pseudocode aufschreiben und jede Aktion entsprechend beschreiben

Bsp Bubblesort

for i = 1 to n do             => Aufwand ~n

     for j = 1 to n do        => Aufwand ~n

          if a[i] < a[j]         => Aufwand ~1

              h = a[i]           => "

              a[i] = a[j]        => "

              a[j] = h           => "

         fi

    endfor

endfor

Induktionsanfang n=1 ist erfüllt

Induktionsschnritt für n => n+1

für n*n+4 => (n*n+c) + (1+1+4) = ((n+1)*(n+1) + c) lösen und und letztendlich kommt auf beiden seiten n^2 + c raus und somit passt das auch

[flashpixx]

für n*n+4 => (n*n+c) + (1+1+4) = ((n+1)*(n+1) + c) lösen und und letztendlich kommt auf beiden seiten n^2 + c raus und somit passt das auch

Das stimmt so nicht,

ich habe für n nach n+1

n*(n+c) + 1+1+c = (n+1)*((n+1)+c)

kommt aber das gleiche bei raus. Ich sortiere n Elemente und dann noch ein weiteres Gegenübergestellt ich sortiere (n+1) Elemente. 1+1+c wäre letztendlich der Aufwand um 1 Element zu sortieren. Beim Umstellen kommt dann links O(n^2) + O(cn) raus da, der lineare Anteil fällt logischerweise weg da O(cn) < O(cn^2) und rechts geht das ganze analog

[lupo49]

Ok, der Aufbau ist nachvollziehbar. Aber wie kommst du darauf dass der Induktionsschluss gleich ist.

n*(n + c) + 1 + 1 + c = (n + 1)*((n + 1) + c) 

n² + n*c + 2 + c = (n + 1) * (n + 1 + c)

n² + n*c + 2 + c = n² + n + n*c + n + 1 + c

n² + n*c + 2 + c = n² + n*c + 2n + 1 + c

[flashpixx]

Ok, der Aufbau ist nachvollziehbar. Aber wie kommst du darauf dass der Induktionsschluss gleich ist.

Weil ich das abschätzen kann. 1+c < c => irgendein konstanter Faktor und O(cn) kann ich garantiert durch O(cn^2) abschätzen, denn O(cn) < O(cn^2).

D.h. im Induktionsschluss ist für lim n->inf wirkt das n^2 am "stärksten".

Landau-Symbole sind Schrankenabschätzungen im Limes.

Natürlich muss man noch einmal überlegen, wie man das konkret beweist, ich habe das jetzt "nur" mal auf die Schnelle gemacht, so dass man sieht wie das Prinzip ist

Bearbeitet 26. Juni 2010 von flashpixx