Я начну с утверждения, что вставка узла в минимальную кучу описывалась в других моих статьях: Построение минимальной кучи из дерева и Создание минимальной кучи из массива.
Вкратце, вы добавляете его в качестве последнего элемента в дереве. Вы сравниваете его с его родителем, и если он больше, вы меняете местами родительский и дочерний. Вы продолжаете сравнивать его с каждым родительским элементом, поднимающимся вверх по дереву, пока не достигнете точки, в которой либо родительский элемент меньше, чем узел, который вы вставляете, либо узел не достиг корня.
Начнем с удаления корневого узла. Причина, по которой мы удаляем корневой узел, связана с основной концепцией кучи: приоритетной очередью. Элемент с наивысшим приоритетом удаляется из очереди приоритетов.
При удалении корневого узла последний узел становится новым корневым узлом.
Корневой элемент может находиться в неправильном месте минимальной кучи. Поскольку 48 больше, чем его дочерние элементы, он должен стекать в правильное положение. Мы будем следовать тому же подходу, что и в статье Построение Min-Heap из дерева.
Производится сравнение двух дочерних элементов, 4 и 7, и выбирается наименьшее значение. Поскольку 4 меньше 48, они меняются местами.
Затем сравниваются 5 и 8, чтобы снова получить самого маленького ребенка из 48. Учитывая, что 5 - самый маленький дочерний элемент, 48 сравнивается с 5. Узел 5 меньше 48, поэтому два узла меняются местами.
Наконец, сравниваются 11 и 6. Узел 6 - самый маленький дочерний элемент, поэтому он по сравнению с 48. Узел 48 больше; поэтому два узла меняются местами. Узлу 48 больше нечего сравнивать. Min-Heap снова достигается после удаления корневого узла.
Если вам понравилось то, что вы прочитали, моя книга Иллюстративное введение в алгоритмы охватывает эту структуру данных и многое другое.
