Кой е най-добрият начин за прилагане на опашка с приоритет с двоен край?

Има много специализирани структури от данни за това. Една проста структура от данни е min-max heap, която е реализирана като двоична купчина, където слоевете се редуват между „min слоеве“ (всеки възел е по-малък или равен на своите наследници) и „максимални слоеве“ (всеки възел е по-голям от или равна на своите наследници.) ​​Минимумът и максимумът могат да бъдат намерени за време O(1) и, както в стандартна двоична купчина, поставянето на опашки и изваждане от опашката може да бъде извършено за време O(log n) време всяко.

Можете също така да използвате структурата на данните за купчина интервал, която е друга специализирана опашка с приоритет за задачата.

Като алтернатива можете да използвате две приоритетни опашки - една, съхраняваща елементи във възходящ ред, и една в низходящ ред. Всеки път, когато вмъкнете стойност, можете да вмъкнете елементи в двете приоритетни опашки и всеки да съхранява указател към другия. След това, когато извадите от опашката min или max, можете да премахнете съответния елемент от другата купчина.

Като още една опция можете да използвате балансирано двоично дърво за търсене, за да съхранявате елементите. След това минимумът и максимумът могат да бъдат намерени за време O(log n) (или O(1), ако кеширате резултатите), а вмъкванията и изтриванията могат да се извършват за време O(log n). Ако използвате C++, можете просто да използвате std::map за това и след това да използвате begin() и rbegin(), за да получите съответно минималната и максималната стойност.

Надявам се това да помогне!

двоична купчина ще ви даде възможност за вмъкване и премахване на минимум в O(log n), а останалите в O(1).

Единствената трудна част е премахването на най-стария елемент, след като масивът е пълен. За целта запазете друг масив:

time[i] = at what position in the heap array is the element 
          added at time i + 100 * k. 

На всеки 100 итерации увеличавате k.

След това, когато масивът се запълни за първи път, премахвате heap[ time[0] ], когато се запълни за втори път, премахвате heap[ time[1] ], ..., когато се запълни за 100-ти път, обвивате и премахвате heap[ time[0] ] отново и т.н. Когато се запълни за k път, премахвате heap[ time[k % 100] ] (100 е размерът на вашия масив).

Не забравяйте също така да актуализирате масива time, когато вмъквате и премахвате елементи.

Премахването на произволен елемент може да бъде направено в O(log n), ако знаете неговата позиция: просто го разменете с последния елемент във вашия хийп масив и отсейте елемента, в който сте разменили.

Ако абсолютно трябва max и min да бъдат O(1), тогава това, което можете да направите, е да създадете свързан списък, където постоянно да следите min, max и size, и след това да свържете всички възли към някакъв вид дървовидна структура, вероятно купчина. Мин., макс. и размер ще бъдат постоянни и тъй като намирането на който и да е възел ще бъде в O(log n), вмъкването и премахването са log n всяко. Изчистването би било тривиално.

Ако вашата опашка е с фиксиран размер, тогава O-нотацията е безсмислена. Всяка O(log n) или дори O(n) операция е по същество O(1), защото n е фиксирано, така че това, което наистина искате, е алгоритъм, който е бърз за дадения набор от данни. Вероятно две паралелни традиционни опашки с приоритет на купчина биха били подходящи (една за висок, една за нисък).

Ако знаете повече за това какви данни имате, може да сте в състояние да направите нещо по-специално предназначено.