1 Тема от tl

  • tl
  • Участник
  • Неактивен
  • Зарегистрирован: 2022-06-26
  • Сообщений: 3

Тема: PriorityQueue c константным временем работы?

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

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

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

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

2 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: PriorityQueue c константным временем работы?

stacks_for_minima позволяет извлекать самый старый элемент из очереди, а не минимальный элемент. Это не то, что обычно нужно от приоритетной очереди.

Сайтe-maxx

3 Ответ от tl Отредактировано tl (2022-06-27 01:03:20)

  • tl
  • Участник
  • Неактивен
  • Зарегистрирован: 2022-06-26
  • Сообщений: 3

Re: PriorityQueue c константным временем работы?

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

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

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

Извлечение элемента:
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();

4 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: PriorityQueue c константным временем работы?

Да, но тогда получается непонятка с этими "removed_elements". Ведь после того как мы извлекли минимум в приоритетной очереди нам надо вернуть следующий по величине минимум, в то время как описанная в статье структура данных даст минимум среди всех позже добавленных элементов.

Сайтe-maxx

5 Ответ от tl

  • tl
  • Участник
  • Неактивен
  • Зарегистрирован: 2022-06-26
  • Сообщений: 3

Re: PriorityQueue c константным временем работы?

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

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