#algorithm #time-complexity #heap #space-complexity
#алгоритм #временная сложность #куча #пространство-сложность
Вопрос:
Я наткнулся на интересный вопрос, который нахожу довольно сложным для себя. Вопрос заключается в следующем: вам дается максимальная куча и значение k. Значение k находится в левой части кучи. Напишите алгоритм, который возвращает индекс, в котором он находится. Попробуйте сделать это в максимально возможной сложности во времени и пространстве.
Моей первоначальной мыслью было использовать двоичный поиск, но я не уверен. Что вы, ребята, думаете?
Комментарии:
1. Это похоже на двоичный поиск, за исключением того, что на самом деле это не «поиск», так как они уже сказали вам, где
kэто было.2. Инвариант максимальной кучи, реализованной в виде двоичного дерева, заключается в том, что родительский элемент всегда больше, чем его 2 дочерних элемента. К сожалению, вы не можете прекратить поиск стороны (как в двоичном поиске), если родительский элемент не меньше значения k. Таким образом, потенциально это переходит в линейный поиск.
3. Вместо того, чтобы просто «я смутно думаю об использовании двоичного поиска», можете ли вы явно написать алгоритм (в псевдокоде или на языке программирования), а затем протестировать его?
4. @user1984 Мое понимание «Ценность находится на левом пути» заключается в том, что мы всегда следуем за левыми детьми
5. Это не похоже на двоичный поиск @Stef, Они могут прекратить поиск пути только в том случае, если родительский элемент меньше значения
k. Следовательно, нет никакой гарантии, что они занимают половину пространства на каждом шаге.