Это не домашняя работа.

Я использую небольшую «очередь с приоритетами» (в настоящее время реализованную как массив) для хранения последних N элементов снаименьшее значение. Это немного медленно - O (N) время вставки предмета. Текущая реализация отслеживает самый большой элемент в массиве и отбрасывает все элементы, которые не помещаются в массив, но я все же хотел бы еще больше сократить количество операций.

ищем алгоритм очереди приоритетов, который соответствует следующим требованиям:

Очередь может быть реализована в виде массива, который имеет фиксированный размер и не может расти. Динамическое распределение памяти во время любой операции очереди строго запрещено.Все, что не помещается в массив, отбрасывается, но в очереди хранятся все самые маленькие элементы, которые когда-либо встречались.Время вставки O (log (N)) (т.е. добавление элемента в очередь должно составлять до O (log (N))).(необязательно) O (1) доступ к * наибольшему * элементу в очереди (в очереди хранятся * наименьшие * элементы, поэтому самый большой элемент будет отброшен первым, и они понадобятся мне для сокращения количества операций)Легко реализовать / понять. В идеале - что-то похожее на бинарный поиск - как только вы поймете это, вы запомните это навсегда.Элементы не должны быть отсортированы в любом случае. Мне просто нужно сохранить N наименьшее значение из когда-либо встречающихся. Когда они понадобятся, я получу доступ ко всем сразу. Так что технически это не обязательно должна быть очередь, мне просто нужно сохранить N последних наименьших значений.

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

Итак, есть еще идеи?

--РЕДАКТИРОВАТЬ--
Я не заинтересован в реализации STL. Реализация STL (предложенная несколькими людьми) работает немного медленнее, чем используемый в настоящее время линейный массив из-за большого количества вызовов функций.

Меня интересует приоритетная очередьалгоритмы, а не реализации.