Структура данных очереди, поддерживающая быстрый поиск k-го самого большого элемента

Я столкнулся с проблемой, которая требует структуры данных Queue, поддерживающей быстрый поиск k-го максимального элемента.

Требования этой структуры данных следующие:

Элементы в очереди не обязательно являются целыми числами, но они должны быть сопоставимы друг с другом, т.е. мы можем сказать, какой из них больше, когда мы сравниваем два элемента (они также могут быть равны).
Структура данных должна поддерживать enqueue (добавляет элемент в хвост) и dequeue (удаляет элемент в голове).
Он может быстро найти k-й самый большой элемент в очереди, примечание pls k не является константой.
Вы можете предположить, что операции enqueue, dequeue и k-й самый большой элемент, находящий все, происходят с одинаковой частотой.

Моя идея - использовать модифицированное сбалансированное двоичное дерево поиска. Дерево такое же, как обычное сбалансированное двоичное дерево поиска, за исключением того, что каждый node _i дополняется другим полем n _i, n _i обозначает количество узлов, содержащихся в поддереве с корнем node _i. Вышеупомянутые операции поддерживаются следующим образом:

Для простоты предположим, что все элементы различны.

Enqueue (x): x сначала вставляется в дерево, предположим, что соответствующий node - node _t, мы добавляем пару (x, указатель на node _t) в очередь.

Dequeue: предположим (e1, node ₁) - это элемент в голове, node ₁ - это указатель на дерево, соответствующее e1. Мы удаляем node ₁ из дерева и удаляем (e1, node ₁) из очереди.

Найденный K-й самый большой элемент: предположим, что root node node _root, его два дочерних элемента node _left и node _right (предположим, что все они существуют), мы сравниваем K с n _root, возможны три случая:

если K < n _left, мы находим K-й наибольший элемент в левом поддереве n _root;
если K > n _root -n _right, мы находим (Kn _root + n _right) - самый большой элемент в правом поддереве n _root;
иначе n _root - это node, который мы хотим.

Временная сложность всех трех операций: O (log _N), где N - количество элементов, находящихся в очереди.

Как ускорить описанные выше операции? С какими структурами данных и как?

Ответ 1

Примечание. Вы не можете достичь лучше, чем O(logn) для всех, в лучшем случае вам нужно "выбрать", который вам больше всего понравится. (В противном случае вы можете сортировать в O(n), подавая массив в DS и запрашивая 1-й, 2-й, 3-й, n-ый элементы)

Использование списка пропуска вместо сбалансированного BST как отсортированной структуры может уменьшить сложность dequeue в среднем случае O(1). Оно делает не влияют на сложность любого другого op.
Чтобы удалить из списка пропусков - все, что вам нужно сделать, - это добраться до элемента с помощью указателя из головы очереди и следовать за ссылками вверх и удалить их. Ожидаемое количество узлов, которые необходимо удалить, равно 1 + 1/2 + 1/4 +... = 2.
найти Kth можно в O(logK), начиная с самого левого node (а не от корня) и прокладывая себе путь до тех пор, пока вы не обнаружите, что у вас есть "больше сыновей", а затем обработать только что найденный node как корень, как и алгоритм в вопросе. Хотя это лучше в асимптотической сложности - постоянный коэффициент двойной.

Ответ 2

Я нашел интересную статью:

Скользящие окна Топ-k запросов на неопределенные потоки, опубликованные в VLDB 2008 и цитируемые 71.

https://www.cse.ust.hk/~yike/wtopk.pdf

VLDB - лучшая конференция в области исследований баз данных, и число цитат доказывает, что структура данных действительно работает.

Документ выглядит довольно сложно, но если вам действительно нужно улучшить структуру данных, я предлагаю вам прочитать эту статью или документы на справочной странице этой статьи.

Ответ 3

Вы также можете использовать дерево пальцев.

Например, очередь приоритетов может быть реализована путем маркировки внутренних узлов минимальным приоритетом своих дочерних элементов в дереве, или индексированный список/массив может быть реализован с помощью маркировки узлов по счету листьев в их дети. Деревья пальцев могут содержать амортизированные O (1) минусы, реверсирование, cdr, O (log n) append и split; и могут быть адаптированы для индексирования или упорядоченных последовательностей.

Также обратите внимание, что быть чисто функциональной структурой делает это хорошим выбором для одновременного использования.