max heap and insertion

Question

У меня есть целочисленный массив размером 10. Мне нужно нарисовать полное двоичное дерево, которое я сделал. Теперь мне нужно вставить три других элемента, используя процедуру siftup. Покажите максимальную кучу после каждой вставки.

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

Определение (максимальная куча) HEAP (X) Пусть X - полностью упорядоченное множество. Куча на X либо пуста, либо ∅, либо представляет собой полное двоичное дерево, t, содержащее nt ≥ 1 узла для каждого узла, для которого присваивается значение X так: значение узла i ≤ значение родительского узла i, i = 2,3, ..., nt. Размер кучи - это количество узлов в дереве. Куча пуста тогда и только тогда, когда ее размер равен 0.

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

Answer 1

Проще говоря, максимальная куча - это куча, где значение родителя больше, чем значение любого из его детей. Когда вы нарисовали свое первоначальное полное двоичное дерево, это уже в виде максимальной кучи? Sift-up (в моем колледже мы назвали его пузырьком, но помимо точки) немного сложно объяснить по такой теме, поэтому я согласен с @DanteisnotaGeek. В статье в Википедии есть хорошая схема того, как работает процедура сортировки. Чтобы показать максимальную кучу после вставки, вы попросите рисовать двоичное дерево, чтобы оно удовлетворяло максимальному количеству кучи после каждой вставки. Таким образом, в конце вы должны иметь свое начальное дерево, дерево с первой вставкой, вторую вставку и третью вставку, так что всего 4 дерева.

Answer 2

Вам необходимо показать полученное дерево после каждого вложения. Я имею в виду, если изначально у вас есть куча

3 
/\ 
1 2 

И вы вставляете 5, она начнется в последней позиции кучи и будет пузыриться до головы кучи:

3   5 
/\  /\ 
    1 2 => 3 2 
/  /
5   1 

Аналогично Если вставить 4, а затем:

5   5 
/\  /\ 
    3 2 => 4 2 
/\  /\ 
1 4  1 3