ограничение размера двоичной кучи первыми N элементами

Question

Я изучал двоичные кучи, и они, очевидно, являются хорошей структурой данных для очереди с приоритетами.Допустим, мой поток данных содержит миллионы (N) записей, и меня периодически интересуют первые 1000 (k << N) записей по рангу.С достаточным пространством я бы просто поддерживал двоичную кучу N-размера, и каждая вставка была бы O (log N).Однако я хотел бы обрезать дерево при каждой вставке, то есть отбрасывать 1001-й элемент.Для меня не очевидно, как сделать обрезку менее чем за O (k) время.</p>

(Если бы я был доволен O (k) временем для каждой обрезки (и вставки), я бы просто вел упорядоченный список из k элементов, а не кучу.)

Одна идеядолжен иметь две параллельные кучи, одна из которых содержит минимальные значения, а другая - максимальные значения, при этом в обоих из них содержатся только первые 1000 элементов.Хотя это немного некрасиво.

Просто чтобы уточнить, вот мои ограничения:

• вставка: в идеале менее ~ 1000 операций (поэтому исключает примитивный список)
• хранение: ограничено, необходимость грубо обрезать непопулярные элементы со скоростью вставки (некоторые издержки с постоянным выводом в порядке)
• запрос топ-1000: топ-1000 элементов не должны быть идеально отсортированы, кучазаказ в порядке

Answer 1

Вы можете сделать это очень легко с помощью двоичной кучи.

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

initialize heap
while (items to be read)
{
    read item
    if (heap.count < 1000 OR item > heap.Peek())
    {
        // Either we haven't added 1,000 items yet,
        // or the new item is larger than the smallest
        // item on the heap.
        heap.Add(item)
        if (heap.count > 1000)
        {
            // trim the heap
            // This makes sure that the heap doesn't
            // grow too large.
            heap.RemoveFirst()
        }
     }
}

(heap.Peek() проверяет, но не удаляет самый низкий элемент в куче).

Когда вы закончите, куча будет содержать 1000 лучших элементов.по рангу.

Этого нельзя сделать за O (N) время.Сложность этого алгоритма составляет O (N log k), где k - размер кучи.

Кстати, упорядоченный список не будет поддерживаться и за O (N).,

Еще один вариант, если вы можете хранить все 1 000 000 элементов в массиве, это Быстрый выбор.Он выполняется за время O (N), но я обнаружил, что когда k мало по сравнению с N, метод выбора кучи работает быстрее.Подробнее см. Когда теория встречается с практикой .

Если вы не можете сохранить все элементы в памяти (т. Е. Работаете с потоком данных), тогда применяется метод выбора кучи.это лучшее, что вы можете сделать.Вы можете сделать то же самое с списком пропусков , который также будет O (n log k), но список пропусков может работать немного лучше, чем двоичная куча.

Кстати, что O (n log k) - наихудший случай, который произошел бы, если бы элементы были представлены в куче в отсортированном порядке.В этом случае каждый элемент добавляется в кучу.Если предметы распределены более нормально, большинство предметов не проходят тест heap.Peek().Мои тесты показывают, что при нормальном распределении только около 10% элементов (при выборе 1000 из 1 000 000) проходят этот первый тест.Снова, больше информации доступно в сообщении в блоге, которое я связал выше.

Answer 2

Звучит так, будто вам нужна Мин-Макс куча .

Это дает вам O (log (n)) операций как для удаления min, так и для удаления max, что должно помочь вам достичьцель.

Answer 3

Куча не подходит для поиска элементов и не сохраняет порядок элементов для сохранения первых 1000 элементов, вы можете сделать это с сбалансированным двоичным деревом поиска в O (n).

Редактировать: Также идея использования минимальной кучи для получения самого большого предмета достаточно хороша, и я не знал об этом, но я предпочитаю BST.