Frage
Der Min-Heap und seine Weiterentwicklungen sind vergleichsbasierte Datenstrukturen. In dieserAufgabe betrachten wir eine dieser weiterentwickickelten Datenstrukturen. Unsere Datenstruktur unterstützt alle Min-Heap-Operationen und hat dabei folgende Laufzeiten:
Operation
| Laufzeit
|
insert (int priority)
| O (1)
|
find-min
| O (1)
|
delete-min
| O (log n)
|
remove (int position)
| O (log n)
|
Die Operation find-min gibt die position und die priority des kleinsten Elements aus. Alle anderen Operationen geben nichts zurück. Die Initialisierung der Datenstruktur ohne Elemente erfolgt in konstanter LaufzeitO(1).
Beweise, dass eine change-priority(int position, int new-priority)Operation nicht in konstanter Laufzeit möglich ist, wenn alle anderen Operationen ihre hier gegebene Laufzeit beibehalten
Ansatz
Tja, da liegt der Hund in der Petersilie begraben. Und warum tut das Tier das? Ich weiß, dass in einem normalen Heap die genannten Operationen alle eine Laufzeit von O (log n) hätten. Hier gehen wir jetzt von dem optimistischen Fall aus, dass insert und find-min in konstanter Laufzeit möglich sind - was ja sehr optimistisch ist. Und trotzdem soll change-priority schlechter als konstant, also schlechter als O (1) sein.
Das wäre doch ohnehin schlechter als O (1). Wenn ich mit change priority an irgendeine Position des Heaps die Zahl ändere, dann muss doch trotzdem der Heap in logaritmischer Zeit durchlaufen werden.Weil die Rotation um den Heap mit change-priortiy zu verwenden dauert doch sowieso O(log(n)). Der Algorithmus muss also eine neue Zahl in den
Min-Heap einfügen, rotieren lassen, das alte Element entfernen und das neue in dem Array speichern. Eine Gesamtlaufzeit um n Elemente in dieser Art und Weise zu sortieren dauert also maximal O(log n) viel Zeit, selbst wenn Insert und find-min konstant sind. Oder hab ich da einen Denkfehler? Wieso komm ich nicht auf die Lösung?
A questa sensa / In diesem Sinne....
Marceline, the Vampire Queen
