Algorithmen und Datenstrukturen · Senior · Frage 74 von 75
Was unterstützt der Trick mit „zwei Heaps“ gegenüber einem balancierten BST nicht effizient?
- 1Ein beliebiges Element aus der Mitte entfernen
- 2Den aktuellen Median in O(1) lesen
- 3Ein neues Element in O(log n) einfügen
Antwort zeigen
Richtige Antwort: Ein beliebiges Element aus der Mitte entfernen
Erklärung
Heaps können nur ihre Wurzel günstig entfernen. Für einen Median im Schiebefenster braucht man Lazy Deletion (entfernte Werte markieren und später überspringen) oder eine geordnete Multimenge wie einen balancierten Baum, der jeden Wert in O(log n) entfernt.