Эффективный список приоритетов

Question

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

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

У кого-нибудь есть лучшее решение?

Answer 1

Кучи кажутся очень подходящими, и кажется, что вы делаете это неправильно.

Скажем, вы хотели, чтобы верхние элементы х (как этот х сравнивается с n, кстати?)

То, что вы делаете, это складываете все в максимальную кучу и получаете топ x.

Я предлагаю вместо этого использовать минимальную кучу ровно x элементов.

Первые x элементов, которые вы вставляете в кучу.

Следующий входящий элемент, вы сравниваете с минимумом, который может быть сделан очень быстро (O (1) время) в куче. Если меньше, вы просто игнорируете входящий элемент.

Если входящий элемент больше чем min, то вы увеличиваете min до входящего элемента и просеиваете его в куче. Это должно быть время logx в худшем случае.

После этого (по времени nlogx) вы можете извлечь элементы из кучи в отсортированном порядке за время O (xlogx).

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

---

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

Вставить элементы в вектор (массив с амортизированным временем вставки O (1)) в порядке их поступления.

Используйте алгоритм Selection, чтобы найти x-й по величине элемент (за O (n) времени, но константы могут быть большими). Скажите, что это число S.

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

Если x имеет разумный размер и сравним с n (например, n / 2 или что-то в этом роде), это может сработать, но если x мало по сравнению с n, я бы предложил использовать минимальную кучу.

Answer 2

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

В операции Add() вы просто сравниваете элемент с наихудшим значением в списке и, если лучше, меняете текущее худшее на добавленный элемент. Это занимает O (k) время в худшем случае для вставки, потому что вам нужно найти элемент, который в настоящее время имеет худший результат. Средний случай, однако, равен O (1) , так как при добавлении более качественных элементов в список вероятность необходимости выполнения свопа стремится к 0 (то есть вы на самом деле не добавление любых предметов).

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

Answer 3

Хм. Пропуск списков ?Они должны иметь вставку O (log n) (как очередь на основе кучи), но верхний элемент должен быть O (1) [включая удаление]Они могут быть даже реализованы с использованием алгоритма без блокировки.

Answer 4

JDK имеет встроенный класс pqueue (java.util.PriorityQueue), основанный на алгоритме кучи.

Извините, я только что увидел, что кучи не соответствуют вашим потребностям. Вы можете объяснить, почему? Вы можете написать собственный компаратор (или сделать ваши элементы сопоставимыми), и PriorityQueue будет заказывать ваши элементы соответствующим образом.