Вставить кучу, удалить k элементов

Question

У меня есть следующая проблема (я думаю, что она хорошо известна / стандартна), о которой я думаю:

Убедитесь, что список k наименьших элементов в двоичной минимальной куче равен O (k).

Я думал об обходе большой мини-кучи в BFS , поддерживая минимальную кучу вместо простой очереди. Первоначально вспомогательная минимальная куча содержит корень моей большой минимальной кучи. На каждом шаге я извлекаю минимум и добавляю всех его потомков (максимум 2). Алгоритм останавливается после k извлечения-минут на вспомогательной минуте-куче. Размер вспомогательной min-heap равен O (k) (для каждого извлеченного min-ключа я вставляю его дочерние элементы, максимум 2).

Проблема в том, что extract-min имеет сложность O (log k), поэтому этот алгоритм имеет сложность O (k log k). И я должен найти один в O (k).

У вас есть какие-нибудь идеи / документы, которые я могу использовать?

Спасибо!

Answer 1

Погуглив «алгоритм выбора кучи», я наткнулся на «алгоритм выбора кучи Фредериксона», который приводит к этой статье (27 страниц ...).

Answer 2

Я думаю, что нашел решение.На каждом шаге вместо выполнения extract-min я выполняю клавишу увеличения.Я искал структуру данных, которая имеет O (1) время наихудшего случая для клавиши увеличения, клавиши вставки и get-min, и обнаружил очередь Бродала .

Для получения дополнительной информации вы можете посмотреть на кучу Фибоначчи , потому что очередь Бродала основана на концепциях, разработанных кучей Фибоначчи.

Итак, на каждом шаге у меня есть следующеепоследовательность операций:

1. min = get-min (вспомогательная куча)

2. пусть (v1, v2) будут дочерними элементами min

3. увеличение-мин (вспомогательная куча, root, v1)

4. вставка (вспомогательная куча, v2)

Каждая из этих 4 операций имеет O (1) сложность наихудшего случая.