Как удалить корневой узел из кучи?

Question

У меня куча: 90 80 80 40 10 20 50. Я должен удалить корневой узел 3 раза. Какой лист займет его место?

Я попытался удалить корневой узел 90 и заменить его на 50, так как он находится в последней позиции кучи. Но я также видел, что можно заменить его на 40, так как это последний оставшийся ребенок. Какое решение является правильным?

Answer 1

Правила удаления корневого узла из двоичной кучи:

1. Замена корневого узла самым нижним, самым правым элементом в куче.
2. Уменьшение количества.
3. Сдвиньте новое значение вниз кучи в новую позицию.

Например, для вашего массива [90, 80, 80, 40, 10, 20, 50] у вас есть куча:

            90
        80      80
      40  10  20  50

Вы удаляете 90 и заменяете на 50, давая вам:

            50
        80      80
      40  10  20

Теперь вы просеиваете вниз.Правила для просеивания таковы, что вы должны поменяться с самым большим из двух детей.В этом случае двое детей равны, поэтому вы можете поменяться с любым из них.Результатом является допустимая куча в любом случае.80 находится сверху, и два узла на следующем уровне либо [80, 50], либо [50, 80].

Причина, по которой вы выбираете самый нижний, самый правый элемент,сохранить свойство кучи.Помните: куча - это полное двоичное дерево со всеми полностью заполненными уровнями, за исключением, возможно, последнего, заполненного слева.Позвольте мне показать вам немного другую кучу, где это может вызвать проблемы:

         90
     66      74
   65  11  70  50

Теперь, если вы должны были заменить 90 на 65, первая проблема, которую вы имеете, это дыра в вашем массиве.То есть у вас будет [65, 66, 74, __, 11, 70, 50].Это было бы достаточно легко исправить, переместив все, что находится за пределами пустого пространства, в левое, и вы получите [65, 66, 74, 11, 70, 50]Но теперь давайте рассмотрим это как кучу:

         65
     66      74
   11  70  50

Правила отсеивания говорят, что вы должны поменяться с самым большим ребенком.В данном случае это 74. Но если вы сделаете это, вы получите недопустимую кучу:

         74
     66      65
   11  70  50

И вы не можете просто решить поменяться с младшим ребенком, потому что если вы это сделаете, то 66 будеткорень.В любом случае вы получите недопустимую кучу.

Существует две причины, по которым вы заменяете корень на самый нижний, самый правый узел (последний элемент в массиве):

1. Корректность.Удаляя последний элемент, вы гарантированно не будете влиять на отношения любых других узлов.Удаление из любого другого места может сделать недействительной кучу.
2. Эффективность.Удалить последний элемент из массива тривиально.Удаление из любого другого места потенциально является операцией O (n).

Answer 2

По определению двоичная куча - это полное двоичное дерево .Это означает, что:

1. Каждый узел имеет либо двух дочерних элементов, либо является листом.
2. Все уровни дерева, кроме, возможно, последнего, полностью заполнены
3. Если последний уровень не завершен, узлы этого уровня заполняются слева направо .

В вашем примере, если вы удалите крайний левый лист (40), третье условие больше не поддерживается: теперь в крайнем левом углу последнего уровня теперь есть пробел.

Единственный узел, который вы можете удалить без , нарушая любое из этих трех условий, - это самый правый лист.Другими словами, это единственный узел, который вы можете удалить для получения формы дерева, который должен иметь конечный результат.

Именно поэтому вам необходимо заменить корневой узел (тот, который вы хотите удалить)с узлом 50 (который удаляется вместо этого, и его значение перезаписывает исходное корневое значение).

Answer 3

Замена на 50 правильна, потому что она сохраняет свойство структур кучи, которые завершены сверху вниз и слева направо.

A complete двоичное дерево - это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы расположены как можно левее.
Следовательно, удаление правого бита удерживает дерево как можно левее.