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

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

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

Что вы делаете, так это помещаете все в максимальную кучу и получаете верхний x.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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