С функциями переключения вверх / вниз
Когда дело доходит до кучи, некоторые из вас могут подумать о структуре двоичного дерева, в которой родительский узел всегда больше или меньше дочерних узлов.
Собственно куча представлена массивом. Просто у него есть специальная схема для манипулирования элементами, чтобы уменьшить временную сложность.
Куча имеет свои основные операции, такие как add (), delete (), size () и т. Д. В этой статье мы представляем новый способ понимания кучи с ее функциями сдвига вверх и вниз.
Вставить новый элемент и сдвинуть вверх
Предположим, у нас есть максимальная куча, и нам нужно добавить новый элемент. Если куча представляет собой массив, мы добавляем его в конец. После этого мы должны выполнить функцию сдвига вверх.
Сформируйте изображения ниже, главный шаг -
сравнивая дочерний элемент с его родительским элементом, если дочерний элемент больше, чем родительский элемент, мы их обмениваем.
Поскольку куча представляет собой древовидную структуру, мы можем легко найти родительский элемент, которым является int (k / 2), где k - текущий дочерний элемент. Остальное можно сделать таким же образом.
Сложность времени: O (logn)
Один совет: не забудьте проверить, входит ли k.
Удалить элемент и сдвинуть вниз
Когда дело доходит до сдвига вниз, у кучи есть особый способ удалить элемент. Мы не можем удалить ни один элемент, который хотим. Как упоминалось в изображениях,
заменяем первый элемент нижним и сдвигаем вниз
Когда мы выполняем сдвиг вниз, мы можем найти его дочерний узел: 2k (слева) и 2k + 1 (справа). Затем мы сравниваем родительский элемент с левым и правым элементом, чтобы найти самый большой элемент для обмена. Если родительский элемент имеет наибольшее значение, мы остаемся на месте.
Сложность времени: O (logn)
Совет: не забудьте убедиться, что k входящий.
Резюме и полный код:
В этой конструкции кучи смещение вверх и смещение вниз является основной частью. Мы можем легко переместить их, потому что легко найти родительские и дочерние элементы.
Если вы изучали кучу раньше, Heapify - популярная концепция. Мы могли бы найти очень сложную функцию heapify, такую как эта:
В этой статье мы упрощаем heapify, определяя местонахождение первого нелистового узла (k / 2) и вызывая shiftDown () в обратном порядке.
Здесь я прикрепил полный код. Надеюсь, вы что-нибудь узнаете из этой статьи. Если вам интересно прочитать какие-либо другие мои статьи, вы можете проверить их в моем профиле. С наилучшими пожеланиями на собеседовании по кодированию!
