Вставка элементов в Двоичную Минимальную "кучу"
Если я вставляю объекты: 10,12,14,1,6 в двоичную минуту помещают один объект в "кучу" за другим, как результаты были бы похожи, моя проблема со следующим
когда я запускаю, я имею:
10
затем
10
/
12
затем
10
/ \
12 14
затем
1
/ \
10 14
/
12
но это не правильно, поэтому что правильный путь состоит в том, чтобы сделать это?
Примечание: это - вопрос о домашней работе, я пытаюсь понять понятие, если Вы не чувствуете себя комфортно, решая вопрос (это не полный вопрос так или иначе), предоставьте примеру подобную проблему.
1 ответ
Вы должны добавить новый элемент в качестве ребенка (или листа именно) в кучу (не как root), что означает, что вы помещаете его в первое «правильное» свободное место (или в вашу кучу-массив, просто в конец).
Тогда вы должны восстановить условия кучи, это называется «HeaPify». Это происходит в двух этапах:
- неоднократно обменивается новым элементом (General: элемент, который нарушает условия кучи) с его родительским узлом до тех пор, пока он меньше, чем родитель, и это не корневой.
- Неоднократно обменивается новым элементом с ребенком с наименьшим значением, пока новый элемент не станет отпуском, или как дочерние узлы больше, чем сам элемент.
Это означает
10
/ \
12 14
+ 1, приводит к
10
/ \
12 14
/
1
, и это нарушает условия кучи, поэтому вы должны вздрогнуть
10
/ \
1 14
/
12
, но это все еще не правильно, так что вы должны снова потребоваться
1
/ \
10 14
/
12
, и там ... все в порядке: -)