Каковы возможные ключи для последней операции вставки? Макс Хип

Question

                             20
                           /    \
                          18     19
                        /   \   /  \   
                      10    13 15   1                      
                      /\    /\ 
                     5 9   8  11

Выше Max-Heap, и это результат после последовательности вставки и удаления максимальных операций. Предположим, что последняя операция была вставлена. Что могло быть возможным ключом для последней операции вставки?

Причина, по которой я не уверен, заключается в том, что в вопросе не указывается, была ли она heapify или нет, так что она могла или не могла быть уже отсортирована. Но опять же я могу ошибаться.

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

Спасибо!

Answer 1

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

Таким образом, если отображаемая куча является кучей после последней операции вставки, то в начале этой вставки в куче должно быть только 10 элементов. Новый предмет был размещен там, где сейчас находится значение 11.

Если предмет был отобран оттуда, то единственные позиции, на которые он мог бы быть просеян, это где цифры 13, 18 и 20 сейчас находятся. Но вставленное число не могло быть 20, потому что если бы оно было, то 18 было бы корнем кучи, и это было бы недействительно (потому что 19 больше 18, и поэтому 19 был бы корнем ).

Таким образом, единственные возможные значения, которые могли быть вставлены последними, это 18, 13 и 11.

Перед вставкой эта ветвь дерева могла бы быть:

• [18,13]: добавление 11 не потребует никаких перестановок.
• [18,11]: добавьте 13, а затем поменяйте местами на 11.
• [13,11]: добавьте 18, а затем поменяйте местами дерево с 11, а затем с 13