Dies ist keine Hausaufgabe.

Ich verwende eine kleine "Prioritätswarteschlange" (derzeit als Array implementiert) zum Speichern der letzten N Elemente mit kleinste Wert. Dies ist etwas langsam - Einfügezeit für O (N) -Elemente. Die aktuelle Implementierung verfolgt das größte Element im Array und verwirft alle Elemente, die nicht in das Array passen. Ich möchte jedoch die Anzahl der Vorgänge weiter reduzieren.

nach einem Prioritätswarteschlangenalgorithmus suchen, der die folgenden Anforderungen erfüllt:

queue kann als Array implementiert werden, das eine feste Größe hat und nicht wachsen kann. Die dynamische Speicherzuweisung während eines Warteschlangenvorgangs ist strengstens untersagt.Alles, was nicht in das Array passt, wird verworfen, aber in der Warteschlange werden alle kleinsten Elemente gespeichert, die jemals angetroffen wurden.O (log (N)) Einfügezeit (d. H. Das Hinzufügen eines Elements zur Warteschlange sollte bis zu O (log (N)) dauern. (optional) O (1) Zugriff für * größtes * Element in der Warteschlange (in der Warteschlange werden * kleinste * Elemente gespeichert, sodass das größte Element zuerst verworfen wird und ich sie benötige, um die Anzahl der Vorgänge zu verringern) Leicht zu implementieren / zu verstehen. Im Idealfall - ähnlich wie bei der binären Suche - können Sie sich nach dem Verständnis für immer daran erinnern.Elemente müssen in keiner Weise sortiert werden. Ich muss nur N kleinsten Wert behalten, der jemals angetroffen wurde. Wenn ich sie brauche, greife ich auf alle gleichzeitig zu. Technisch muss es also keine Warteschlange sein, sondern es müssen nur N kleinste Werte gespeichert werden.

Ich dachte anfangs über die Verwendung von binären Heaps nach (sie können leicht über Arrays implementiert werden), aber anscheinend verhalten sie sich nicht gut, wenn das Array nicht mehr wachsen kann. Verknüpfte Listen und Arrays benötigen zusätzliche Zeit, um sich fortzubewegen. Die stl-Prioritätswarteschlange wächst und verwendet die dynamische Zuordnung (Ikan irre dich aber).

Also, irgendwelche anderen Ideen?

--BEARBEITEN-
Ich bin nicht an einer STL-Implementierung interessiert. Die STL-Implementierung (von einigen Leuten vorgeschlagen) arbeitet aufgrund der hohen Anzahl von Funktionsaufrufen etwas langsamer als das derzeit verwendete lineare Array.

Ich interessiere mich für die Prioritätswarteschlange Algorithmen, keine Implemnetationen.