Простое объяснение алгоритма выбора кучи Фредериксона

Question

Есть ли какое-нибудь простое объяснение алгоритма выбора кучи Фредериксона, чтобы найти элемент k-го ранга за O(k) время в минимальной куче, доступной где-либо онлайн? Если нет, может кто-нибудь объяснить интуицию алгоритма?

Answer 1

Попробуйте прибегнуть к помощи "Выбор кучи Фредериксона"

http://160592857366.free.fr/joe/ebooks/ShareData/An%20Optimal%20Algorithm%20for%20Selection%20in%20a%20Min-Heap.pdf