Wie behalte ich effizient den Überblick über das kleinste Element in einer Sammlung?

Question

Im Sinne von Programmierfragen:Angenommen, es gibt eine Sammlung von Objekten, die miteinander verglichen und sortiert werden können.Was ist die effizienteste Möglichkeit, den Überblick über das kleinste Element in der Sammlung zu behalten, wenn Objekte hinzugefügt und das aktuell kleinste gelegentlich entfernt werden?

Answer 1

Die Verwendung eines Min-Heaps ist der beste Weg.

http://en.wikipedia.org/wiki/Heap_(data_structure)

Es ist maßgeschneidert für diese Anwendung.

Answer 2

Wenn Sie zufälliges Einfügen und Entfernen benötigen, ist ein sortiertes Array wahrscheinlich die beste Lösung.Einfügungen und Entfernungen sollten O(log(n)) sein.

Answer 3

@Harpreet
Das ist nicht optimal.Wenn ein Objekt entfernt wird, muss Erickson die gesamte Sammlung durchsuchen, um das neue Kleinste zu finden.

Sie möchten sich darüber informieren Binärer Suchbaum'S.MS hat ein gutes Website den Weg beginnen.Aber vielleicht möchten Sie sich ein Buch wie dieses besorgen Einführung in Algorithmen (Cormen, Leiserson, Rivest, Stein) wenn Sie tief eintauchen möchten.

Answer 4

Für gelegentliche Entfernungen a Fibonacci-Haufen ist sogar schneller als der Min-Heap.Das Einfügen ist O(1) und das Finden des Minimums ist ebenfalls O(1).Entfernung ist O(log(n))

Answer 5

Wenn Sie zufällige Einsätze und Entfernen benötigen, ist der beste Weg wahrscheinlich ein sortiertes Array.Einfügungen und Entfernungen sollten o (log (n)) sein.

Ja, aber Sie müssen bei jeder Einfügung und (vielleicht) bei jeder Löschung neu sortieren, was, wie Sie sagten, O(log(n)) ist.

Mit der von Harpreet vorgeschlagenen Lösung:

• Sie haben am Anfang einen O(n)-Durchlauf, um das kleinste Element zu finden
• Die Einfügungen sind danach O(1) (nur ein Vergleich mit dem bereits bekannten kleinsten Element erforderlich)
• Löschvorgänge sind O(n), da Sie das kleinste Element erneut finden müssen (denken Sie daran, dass die Big-O-Notation der schlimmste Fall ist).Sie können die Optimierung auch durchführen, indem Sie prüfen, ob das zu löschende Element das (bekannte) kleinste Element ist. Wenn nicht, führen Sie einfach keine erneute Prüfung durch, um das kleinste Element zu finden.

Es kommt also darauf an.Einer dieser Algorithmen eignet sich besser für einen Anwendungsfall mit vielen Einfügungen und wenigen Löschvorgängen, der andere ist jedoch insgesamt konsistenter.Ich glaube, ich würde standardmäßig den Harpreet-Mechanismus verwenden, es sei denn, ich wüsste, dass die kleinste Zahl häufig entfernt wird, da dies eine Schwachstelle in diesem Algorithmus aufdeckt.

Answer 6

Harpreet:

Die Einfügungen wären linear, da Sie Elemente für eine Einfügung verschieben müssen.

Hängt das nicht von der Umsetzung der Sammlung ab?Wenn es sich wie eine verknüpfte Liste verhält, wären die Einfügungen O(1), während es, wie Sie angegeben haben, linear wäre, wenn es wie ein Array implementiert würde.

Answer 7

Hängt davon ab, welche Vorgänge Ihr Container unterstützen soll.A Min-Heap ist die beste Option, wenn Sie das min-Element zu einem bestimmten Zeitpunkt entfernen müssen, obwohl mehrere Vorgänge nicht trivial sind (amortisierte log(n)-Zeit in einigen Fällen).

Wenn Sie jedoch nur von vorne/hinten drücken/poppen müssen, können Sie einfach eine Mindeque verwenden, die eine amortisierte konstante Zeit für alle Vorgänge (einschließlich findmin) erreicht.Du kannst tun eine Suche auf Scholar.google.com um mehr über diese Struktur zu erfahren.Ein Freund und ich haben kürzlich zusammengearbeitet, um auch eine viel einfacher zu verstehende und umsetzbare Version einer Mindeque zu entwickeln.Wenn Sie danach suchen, könnte ich die Details für Sie posten.