Limit Orderbuch: Datenstruktur zur Verwaltung der Kauf-/Verkaufsauftragsliste

Question

Ich möchte ein Limit-Orderbuch erstellen, das eine Kauf-/Verkaufsauftragsliste enthält. Für die Kaufauftragsliste sollte der höchste Kaufwert zuerst in der Liste und für die Verkaufsauftragsliste der niedrigste Verkaufswert zuerst in der Liste sein. Für neu kommende Bestellung möchte ich den richtigen Platz zum Einfügen in die Liste bekommen.

Derzeit bin ich mit linearer Suche einfügen, aber es dauert O (n) Zeit, die für Millionen von Ordnung sehr hoch ist.

Gibt es eine Datenstruktur, die den Knoten in sortierter verknüpfter Liste in O (log n) oder weniger Zeit einfügen kann?

Answer 1

den Knoten in sortierte verknüpfte Liste in O (log n) oder weniger Zeit einfügen?

Nein, das ist nicht möglich.

auch immer Sie einen binären Suchbaum oder einen min Heap verwenden kann (wenn Sie nur die Min- oder Max zu einem Zeitpunkt wollen), um die Daten zu speichern. Ein ausgewogener binärer Suchbaum würde Ihre Daten sortiert halten und das Einfügen/Löschen in O (log n) Zeit vornehmen.