Algorithmen und Datenstrukturen · Senior · Frage 41 von 75
Welche Komplexität hat das Aufbauen eines binären Heaps aus n unsortierten Elementen per Sift-down (Heapify)?
- 1O(n)
- 2O(log n)
- 3O(n log n)
Antwort zeigen
Richtige Antwort: O(n)
Erklärung
Die meisten Knoten liegen nahe dem Boden und sinken nur wenig ab: die Hälfte bewegt sich 0 Ebenen, ein Viertel 1 Ebene und so weiter. Die Summe konvergiert gegen O(n). Elemente einzeln einzufügen wäre O(n log n).