Datenstruktur, die immer n-beste Elemente enthält

Die gewünschte Datenstruktur ist wahrscheinlich der implizite Heap . Die rohe Datenstruktur ist nur ein Array; Nennen Sie für die Bequemlichkeit, dass es N = 2 ^ n Elemente in der Größe ist, und dass Sie die größten N-1 Elemente beibehalten möchten.

Die Idee ist, das Array (nennen wir es A) als kompletten binären Baum der Tiefe n zu behandeln:

• ignoriere A [0]; behandle A [1] als Wurzelknoten
• für jeden Knoten A [k] sind die Kinder A [2 * k] und A [2 * k + 1]
• Knoten A [N / 2..N-1] sind die Blätter

Um den Baum als "Heap" zu erhalten, müssen Sie sicherstellen, dass jeder Knoten kleiner als (oder gleich) seinen Kindern ist. Dies wird "Heap-Bedingung" genannt:

• A [k] & lt; A [2 * k]
• A [k] & lt; = A [2 * k + 1]

So verwenden Sie den Heap, um die größten N-Elemente zu verwalten:

• Beachten Sie, dass die Wurzel A [1] das kleinste Element im Heap ist.
• vergleiche jedes neue Element (x) mit der Wurzel: Wenn es kleiner ist (x & lt; A [1]), lehne es ab.
• Andernfalls fügen Sie das neue Element wie folgt in den Heap ein:
  • Entfernen Sie die Wurzel (A [1], das kleinste Element) aus dem Heap, und lehnen Sie sie ab
  • ersetze es durch das neue Element (A [1]: = x)
  • Stellen Sie jetzt die Heap-Bedingung wieder her:
    • Wenn x kleiner oder gleich seinen beiden Kindern ist, sind Sie fertig
    • andernfalls tauschen Sie x mit dem kleinsten Kind aus
    • Wiederholen Sie den Test und den Austausch an jeder neuen Position, bis die Heap-Bedingung erfüllt ist

Im Grunde wird jedes Ersatzelement den Baum "filtern", bis er seinen natürlichen Platz erreicht hat. Dies wird höchstens n = log2 (N) Schritte dauern, was so gut wie möglich ist. Außerdem ermöglicht die implizite Form des Baums eine sehr schnelle Implementierung; Bestehende Bibliotheken mit eingeschränkter Priorität werden höchstwahrscheinlich einen impliziten Heap verwenden.

Eine Prioritätswarteschlange ist in C ++ mit STL am nächsten. Sie könnten es in eine andere Klasse einfügen, um eine eigene Implementierung zu erstellen, die die Größe automatisch anpasst.

Sprach-agnostisch (obwohl vielleicht nicht Speicher-Fragmentierung-sicher):

1. Daten einfügen
2. Sortieren
3. Lösche alles nach dem n-ten Element

std :: priority_queue macht Schritt 2 für Sie.

In Java können Sie ein SortedSet verwenden, das z. von einem TreeSet. Prüfen Sie nach jedem Einfügen, ob die Menge zu groß ist. Wenn ja, entfernen Sie das letzte Element.

Dies ist einigermaßen effizient, ich habe es erfolgreich für die Lösung mehrerer Project Euler-Probleme verwendet.

Eine beschränkte Prioritätswarteschlange , denke ich ... Java hat so etwas in seiner Standardbibliothek. BEARBEITEN : Es heißt LinkedBlockingQueue . Ich bin mir nicht sicher, ob die C ++ STL etwas ähnliches enthält.

Ist es nicht möglich, die ersten n Elemente aus einer sortierten Sammlung zu übernehmen?

Ja, Sie können einen minimalen Kopf der Größe N beibehalten Dann vergleichen Sie das neue Element mit dem Stammelement bei jedem Einfügen Pop die Wurzel und fügen Sie das Element ein, wenn es "größer" als die Wurzel ist Schließlich enden Sie mit N größten Items