максимальная куча и вставка

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

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

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

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


algorithm data-structures heap binary-tree max-heap
person johnnily    schedule 25.11.2012    source источник
comment
the definition of max heap is like this, but it looks like a bit ambiguous to me. Какая часть кажется вам двусмысленной? Это именно та часть, на которой вам нужно сосредоточить свой вопрос.   -  person phant0m    schedule 25.11.2012

Ответы (3)


arrow_upward
4
arrow_downward

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

person masotann    schedule 25.11.2012

arrow_upward
9
arrow_downward

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

   3
  / \
 1   2

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

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

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

    5           5
   / \         / \
  3   2  =>   4   2
 / \         / \
1   4       1   3
person Juan Lopes    schedule 25.11.2012
comment
этот ответ заслуживает гораздо большего количества голосов, спасибо за отличную демонстрацию. - person M.kazem Akhgary; 22.01.2018

arrow_upward
1
arrow_downward

В куче в любой момент времени от корневого узла до конечного узла упорядочено и линейно:

введите здесь описание изображения

При вставке элемента в следующий слот в куче порядок строк будет изменен: введите здесь описание изображения

Итак, последним шагом вставки становится изменение порядка линейной структуры данных: сортировка пузырьком

person 宏杰李    schedule 24.03.2018