Эффективный список приоритетов
Я ищу эффективную структуру данных для представления списка приоритетов. Конкретно я должен присвоить приоритет ряду объектов и возвратить только главные объекты выигрыша. Я изучил приоритетные очереди, которые воздействуют на "кучу", но они, кажется, действительно не удовлетворяют моим потребностям. Они реорганизуют структуру "кучи", как только я опрошу главный объект оценки от очереди.
Простое решение, конечно, было бы связанным списком, который в худшем случае возьмет, вполне жаждут операции вставки.
У кого-либо есть лучшее решение?
4 ответа
Кучи кажутся очень подходящими, и похоже, что вы делаете это неправильно.
Допустим, вам нужны верхние x элементов (как этот x сравнивается с n, кстати?)
Вы помещаете все в максимальную кучу и получаете верхние x.
Я предлагаю вместо этого использовать минимальную кучу ровно из x элементов.
Первые x элементов, которые вы вставляете в кучу.
Следующий входящий элемент вы сравниваете с минимальным, что можно сделать очень быстро (время O (1)) в куче. Если меньше, вы просто игнорируете входящий элемент.
Если входящий элемент больше min, вы увеличиваете min до входящего элемента и отсеиваете его в куче. В худшем случае это должно быть время logx.
После выполнения (за время nlogx) вы можете извлекать элементы из кучи в отсортированном порядке за время O (xlogx).
В зависимости от того, каковы ваши данные (и насколько мало x), использование этого решения с минимальной кучей может быть очень быстрым.
Если вы действительно хотите, чтобы вставки были сверхбыстрыми и не заботились об извлечении, вы также можете сделать следующее.
Вставьте элементы в вектор (массив с амортизированным временем вставки O (1)) в порядке их поступления.
Использование алгоритма выбора для нахождения x-го наибольшего элемента (за время O (n), но константы могут быть большими). Скажем, что это число S.
Теперь пройдемся по массиву, сравнивая каждый элемент с S и выбери те, которые имеют размер S.
Если x имеет разумный размер и сопоставим с n (например, n / 2 или что-то в этом роде), это может сработать, но если x мало по сравнению с n, я бы посоветовал использовать min-heap.
JDK имеет встроенный класс pqueue (java.util.PriorityQueue), который основан на алгоритме кучи.
Извините, я только что увидел информацию о кучах, которые вам не подходят. Вы можете объяснить почему? Вы можете написать собственный компаратор (или сделать свои элементы сопоставимыми), и PriorityQueue упорядочит ваши элементы соответствующим образом.
Хм. Пропустить списки ? Они должны иметь вставку O (log n) (как очередь на основе кучи), но получение верхнего элемента должно быть O (1) [включая его удаление]. Они могут быть реализованы даже с использованием алгоритма lock-free.
Если вам нужны только k верхние элементы, и вам никогда не нужно искать другие, вы можете использовать простой связанный список или массив, хранящий только текущие верхние k элементов плюс число (наихудшая оценка элементов в списке).
В операции Add () вы просто сравниваете элемент с наихудшим значением в списке и, если лучше, меняете текущее худшее значение с добавленным элементом. Это занимает O (k) времени в наихудшем случае для вставки, потому что вам нужно найти элемент, который в настоящее время имеет наихудший результат. В среднем, однако, это O (1) , поскольку, когда вы добавляете лучшие элементы в список, вероятность необходимости выполнить замену стремится к 0 (то есть вы на самом деле не добавление любых предметов).
Таким образом, если вы генерируете элементы случайным образом, ваша производительность, вероятно, будет очень хорошей. Даже если вы создаете заказанные товары (худший случай), этого может быть достаточно для вашего значения k .