Приоритетная очередь с произвольным доступом

Question

У меня есть очередь с приоритетами, которая сортирует элементы по некоторому значению (назовем его рейтинг).Мне нужно взять элементы из очереди по рейтингу.Поэтому мне нужно реализовать функцию queue_get (rating).Эта функция также повышает рейтинг, что нормально с кучей приоритетов.

Но проблема в том, что каждый уровень кучи не упорядочен по рейтингу.Элементы каждого уровня удовлетворяют только свойству кучи.Поэтому я не могу точно вернуть N-й элемент по рейтингу.

Есть ли реализации приоритетной очереди с такой функциональностью?Должен ли я использовать другую структуру данных?

Answer 1

Самое простое решение состоит в том, чтобы использовать двоичное дерево поиска, которое является самобалансирующимся, например, Дерево AVL, дерево из массива или красно-черное дерево. Он позволяет получить доступ к элементам по их ключу за O (log n) и перебрать объекты в их порядке в O (log n + k), где k - количество повторяемых элементов.

Answer 2

Класс коллекции обычно дает вам некоторую карту, основанную на упорядоченном ключе, например, java.util.TreeMap или C ++ std :: map.Используя это, вы можете извлекать элементы в отсортированном порядке - вам, возможно, придется инвертировать порядок, если класс дает вам элементы в возрастающем порядке.Если все, что вы хотите сделать, это прочитать верхние N элементов, этого должно быть достаточно для вас.

Если вы хотите произвольный доступ к N-му самому высокому элементу, это можно сделать, пометив древовидную структуру данных числомэлементов под каждым узлом, но я не знаю о широко доступной библиотеке классов, которая дает вам это.

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