Ich versuche also, eine Datenstruktur zu implementieren, um die dynamische Ordnungsstatistik zu verarbeiten. Die Datenstruktur hat folgende Operationen:
Ich habe meine Datenstruktur mit einem ausgewogenen AVL-Tree implementiert. Damit haben die Operationen folgende zeitliche Komplexität:
Hier ist meine Implementierung für die get (k) die O (log (n)) Zeit verwendet:
%Vor%Und hier ist meine Implementierung für die Knotenklasse:
%Vor%}
Meine Aufgabe besteht jedoch darin, eine Datenstruktur zu implementieren, die die obigen Operationen verarbeiten kann, und nur eine O (1) (konstante) Zeit für die Operation get (k) zu verwenden. (Und addiere (x) immer noch O (log (n)) Zeit). Außerdem darf ich keine Hashmaps verwenden.
Ist es möglich, meine Implementierung zu modifizieren, um konstante Zeit zu bekommen? Oder welche Art von Datenstruktur kann die get (k) Operation in konstanter Zeit verarbeiten?
Soweit ich verstehe, wächst der k-Parameter grundsätzlich mit der Größe der Elemente, was bedeutet, dass Sie für jedes n den genauen Wert von k kennen.
Wenn das der Fall ist, dann ist mein Vorschlag, einen Max-Heap und einen Min-Heap zu verwenden. Der Max-Heap organisiert Elemente (kleiner als das n / a-te Element) in einer Heap-Struktur, die den Zugriff auf das größte Element (Root) in konstanter Zeit ermöglichen. Dementsprechend organisiert der Min-Heap Elemente (größer als das n / a-te Element) in einer Heap-Struktur, die den Zugriff auf das kleinste Element (Root) in konstanter Zeit ermöglichen.
Wenn neue Elemente ankommen (hinzufügen), platzieren Sie sie im entsprechenden Heap in O (log n). Wenn der Max-Heap größer oder kleiner als (n / a) wird, führen Sie einen Neuausgleich zwischen den beiden Heaps in O (log n) durch
Ihre Funktion get () muss jetzt nur das Wurzelelement des Max-Heap in O (1) zurückgeben.
In Java können Sie eine Prioritätswarteschlange für den Max-Heap (und Min-Heap) verwenden
%Vor%Die Klasse könnte so aussehen
%Vor%Bearbeiten (von Cheaty McCheatFace):
Eine weitere Idee, mit der Sie Ihren Code verwenden können, ist aber etwas betrügerisch: Wann immer Sie ein Element zu Ihrem AVL-Tree hinzufügen, berechnen Sie das k (= n / a) größte Element (wie in Ihrem Code) und speichern es. Auf diese Weise hat die add () - Funktion immer noch eine O (log n) Laufzeit. Die get () - Funktion ruft nur den gespeicherten Wert ab und befindet sich in O (1).
Wenn Sie Bäume verwenden möchten, behalten Sie eine Reihenfolge zwischen 1 und maximal a balanced trees bei. Bewahren Sie für jeden Baum einen Zeiger auf das kleinste und größte Element sowie die Baumgröße auf. Wenn ein Element hinzugefügt wird, fügen Sie es in die entsprechende Struktur ein. Wenn ein Baum über ceiling(n / a) elements hinaus wächst, reorganisiere die Bäume, indem du das entsprechende niedrigste oder höchste Element in einen benachbarten Baum verschiebst, um alle zwischen floor(n / a) und ceiling(n / a) Elementen in der Größe zu halten. Das Element k th wird immer entweder der kleinste oder der höchste einer der Bäume sein.
Add würde O(log a + log(n/a) * a) = O(log n) time benötigen.
Get würde O(log a) = O(1) time übernehmen.
Tags und Links algorithm java data-structures binary-search-tree avl-tree