Вставка элементов в Бинарный Min кучи

Question

Если я вставлять элементы: 10,12,14,1,6 в двоичную мин кучу один пункт за другие, как бы результаты выглядеть, моя проблема заключается в следующем

когда я начала у меня есть:

10 

затем

10 
/
12 

затем

10 
/\ 
12 14 

затем

1 
/\ 
10 14 
/
12 

, но это не правильно, так что это правильный способ сделать это?

Примечание: это вопрос домашней работы, я пытаюсь понять концепцию, если вы не чувствуете себя комфортно, решая вопрос (в любом случае, это не полный вопрос), пожалуйста, укажите пример с аналогичной проблемой.

Answer 1

Вы должны добавить новый элемент в виде дочернего элемента (или листа точно) в кучу (не как root), что означает, что вы помещаете его в первое «правильное» свободное место (или в ваш массив кучи, просто в конце).

Затем вы должны восстановить условия кучи, это называется «heapify». Это происходит в два этапа:

1. Многократно обменивать новый элемент (общий: элемент, который нарушает условия кучи) с родительским узлом, пока он меньше, чем родитель, и это не является корнем.
2. Неоднократно обменивается новым элементом с дочерним элементом с наименьшим значением, пока новый элемент не станет уходом, или оба дочерних узла больше самого элемента.

Это означает, что

10 
/\ 
12 14 

+ 1 приводит к

10 
/\ 
12 14 
/
1 

И что нарушает условия кучи, так что вы должны heapify

10 
/\ 
    1 14 
/
12 

Но это еще не правильно, поэтому вам нужно снова наследовать

 1 
/\ 
10 14 
/
12 

И вы ... все в порядке :-) Теперь

Answer 2

step1:  10 
step2:  10 
     /
     12 
step3:  10 
     /\ 
     12 14 
step4:  1 
     /\ 
     10 12 
     /
     14 
step5:  1 
     /\ 
     6 10 
     /\ 
     12 14