0
Я думаю, что при вставке нового узла в кучу количество узлов, которое он может пройти, это logN, почему это (1 + logN), где 1 из?Почему при вставке нового узла в кучу требуется не более 1 + logN?
A
ответ
2
Это необходимо для учета пограничного случая, когда количество нот составляет 2 n. Куча п уровней соответствует 2 п -1 объектов, так что добавление еще один объект начинает новый уровень:
Черные квадраты представляют семь элементов кучи три уровня. Красный элемент - номер восемь. Если ваш поиск приведет вас к местоположению этого последнего элемента, вы получите четыре сравнения, хотя журнал 8 - три.
+0
спасибо за ваш ответ. Но я не понимаю, почему есть 4 сравнения. Для меня это кажется только 3 раза, даже если новый добавленный красный квадрат переместится до корня (три сравнения: красная линия, зеленая линия и синяя линия, всего 3 раза) – user1888955
+0
@ user1888955 Вам нужно сравнить с корнем, корневым корнем , внука корня и самого красного узла, чтобы убедиться, что вы нашли предмет, который вы ищете. – dasblinkenlight
+0
Спасибо за ваш быстрый ответ :) Я пропустил сравнение на самом узле. – user1888955
Потому что 'log (1) = 0', но вставка в кучу с 1 элементом принимает сравнение – harold
Спасибо за ваш ответ. Я думаю, что это должен быть правильный ответ. – user1888955