Вставить / удалить тот же элемент в сортировке кучи

Question

Показать кучу на каждом этапе, когда следующие числа вставляются в изначально пустую мин-кучу в указанном порядке: {11, 17, 13, 4, 4, 1 }. Теперь покажите кучу на каждом этапе, когда мы последовательно выполняем операцию удаления в куче, пока она не станет пустой.

Вот ответ / контрольная точка, которую я получаю:

![1]https://imgur.com/zu47RIF

У меня есть 2вопросы, пожалуйста:

1. Я не понимаю, когда мы вставляем элемент 4 во второй раз, почему мы сдвигаем 11, чтобы сделать его правильным потомком старого элемента / во-первыхвставленный элемент 4? Это потому, что мы хотим удовлетворить требование полного двоичного дерева, то есть каждый узел на уровнях от 1 до k - 2 имеет ровно 2 дочерних элемента (k = уровни деревьев, уровень k - самый нижний уровень)?

2. Я не понимаю, как мы deleteMin = 1, 13 становимся правым потомком вновь родителя 11 (который является левым потомком 4),Просто быстрое замечание, что мой инструктор дал классу 2 способа удаления мин. Другой способ мне подходит - это просто обратный процесс вставки.

Answer 1

1. Как вы сказали, форма кучи - это «почти полное дерево»: все уровни завершены, кроме самого нижнего уровня, который может быть неполным справа. Поэтому второй 4 обязательно добавляется справа от 17, чтобы сохранить форму кучи:

        4
      /   \
    11     13
  /    \
17      4

После этого 4 переключается с помощью 11 для восстановлениясвойство min-heap.

Удаление, как правило, осуществляется путем удаления корневого элемента и помещения последнего (т.е. самого нижнего правого) элемента на его место. Это сохраняет форму кучи. Затем новому корню разрешается просеять, чтобы восстановить свойство min-heap. Таким образом, 13 становится новым корнем:

        13
      /    \
    4       4
  /   \
17     11

Затем 13 поменяется местами с любым дочерним узлом. Похоже, они выбрали правую руку в вашем примере.