Algorithmen und Datenstrukturen · Middle · Frage 10 von 75
Was kosten die Hauptoperationen eines binären Heaps?
- 1Peek O(log n), Einfügen O(1), Minimum entnehmen O(1)
- 2Peek O(1), Einfügen O(n), Minimum entnehmen O(n)
- 3Peek O(1), Einfügen O(log n), Minimum entnehmen O(log n)
Antwort zeigen
Richtige Antwort: Peek O(1), Einfügen O(log n), Minimum entnehmen O(log n)
Erklärung
Das Minimum sitzt an der Wurzel. Einfügen hängt ans Ende an und lässt es „aufsteigen“; Entnehmen setzt das letzte Element an die Wurzel und lässt es „absinken“. Beides läuft einen Pfad der Höhe log n entlang.