1 Ответ от tl

(4 ответов, оставленных в Algo)

я кажется понял, где это ломается:

как только очередь будет опустошена обычным pop_front (до этого вывод будет совпадать с выводом приоритетной очереди), следующий pop_front должен будет искать минимум в removedElements - что убивает константу.

Перейти к разделу: Algo

2 Ответ от tl

(4 ответов, оставленных в Algo)

Спасибо за быстрый ответ!

самый старый элемент из очереди, а не минимальный элемент.

это наверное про

Извлечение элемента:
if (!q.empty() && q.front() == removed_element)
    q.pop_front();

я имел в виду такой метод вообще не использовать, а использовать только add & front из статьи, что-то вроде

add():

while (!q.empty() && q.back() > added_element) {
    removed_elements(q.back()); //  не теряем элементы
    q.pop_back();
        
}
q.push_back (added_element);

в качестве poll мы отдаем первый элемент в очереди, то есть реальный минимум
current_minimum = q.front();

Перейти к разделу: Algo

3 Тема от tl

(4 ответов, оставленных в Algo)

В статье https://e-maxx.ru/algo/stacks_for_minima о модификации стека и очереди для нахождения минимума за O (1) описан вариант 1, который обладает следующими особенностями:

1. Элементы хранятся в неубывающем порядке
2. Некоторые элементы могут быть удалены во время вызова add()

Если копировать удаленные элементы в другой список, мы получаем крутую приоритетную очередь - добавление за константу (согласно статье), получение/удаление минимума это просто peek/poll и тоже константа!,  size это сумма размера очереди и размера хранилища удаленных элементов.

Понятно, что poll в цикле не даст отсортированный массив (вроде как одна явная разница) - но можно просто скомбинировать очереди и удаленные элементы и отсортировать если имеется такая необходимость. В чем еще может быть подвох - иначе такая структура выглядит лучше двоичной кучи по всем параметрам

Перейти к разделу: Algo