Поиск всех чисел в куче, которая меньше, чем k в линейном времени

Question

Учитывая кучу и некоторое число k в куче, как я могу найти числа r, которые меньше, чем k в O (r)?

Мне был предложен алгоритм, который я не понимаю: Перемещение с предварительным порядком в куче, а в то время как значения меньше, чем k (и! = Null), напечатайте их. И, предположительно, это берет O (3r + 1) = O (r) проверок.

Может ли кто-нибудь объяснить мне решение? Благодаря!

Answer 1

Единственные цифры, которые нужно посетить в куче, - это числа, меньшие, чем k, и их ближайшие дети. Как только вы увидите, что ребенок слишком велик, вы знаете, что вам не нужно смотреть на своих детей. Каждое число в куче имеет не более двух детей, поэтому это ограничивает около 2r на числа, которые вы посещаете, что вам не нужно (ясно, что r = 0 - особый случай).