Как лучше всего реализовать двустороннюю очередь с приоритетом?

Для этого существует множество специализированных структур данных. Одной из простых структур данных является куча min-max, которая реализована как двоичная куча, в которой слои чередуются между «минимальными слоями» (каждый узел меньше или равен своим потомкам) и «максимальными слоями» (каждый узел больше чем или равно его потомкам.) Минимум и максимум могут быть найдены за время 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] ], ..., когда он заполнится в сотый раз, вы перевернете и снова удалите 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 фиксировано, поэтому вам действительно нужен алгоритм, быстрый для данного набора данных. Вероятно, две параллельные традиционные очереди с приоритетом кучи были бы в порядке (одна для высокого, другая для низкого).

Если вы знаете больше о том, какие данные у вас есть, возможно, вы сможете сделать что-то более специальное.