В двоичной максимальной куче, реализованной как двоичное дерево (где каждый узел хранит указатель на своего родителя, левого дочернего и правого дочерних элементов), если у вас есть указатель на корень кучи, как бы вы реализовали операцию вставки? Что должно произойти, так это то, что узел первым вставляется как последний элемент в последней строке. Для массива вы можете добавить его к массиву, но для реализации на основе дерева, как бы вы нашли нужное место?
Как вставить в двоичную максимальную кучу, реализованную в виде двоичного дерева?
comment
Какова форма этого связанного списка? Если родители не могут обязательно указывать на своих детей, то в каком порядке связаны узлы?
- person templatetypedef schedule 09.02.2013
comment
Связанный список будет выглядеть так: en.wikipedia.org/wiki/Binary_heap Итак, каждый узел, будет иметь указатель на своего родителя, левого дочернего элемента, правого дочернего элемента и значение ключа. Нулевое значение, если это корень или нет дочерних элементов.
- person omega schedule 09.02.2013
comment
@ omega- Ну ладно. Это не двусвязное представление двоичной кучи в виде списка; это представление в виде дерева.
- person templatetypedef schedule 09.02.2013
comment
да, но это не вдвойне одно и то же, потому что у вас есть указатели, идущие в обоих направлениях (родитель к потомку и потомок к родителю)?
- person omega schedule 09.02.2013
comment
@ omega- Они имеют одинаковое представление, но двусвязный список - это совершенно другая структура, чем общая древовидная структура. Двусвязный список - это особый случай дерева, где каждый узел указывает на своих дочерних элементов и на своего родителя, поэтому было бы неправильно описывать представление дерева как связанный список.
- person templatetypedef schedule 09.02.2013
comment
Но в моем случае узлы действительно имеют указатель на своих 2 дочерних элемента и родителя, так что разве это не сделает его двусвязным списком? (я упомянул об этом два комментария назад и в основном сообщении)
- person omega schedule 09.02.2013
comment
@ omega- Нет. Двусвязный список, в частности, подразумевает, что вы можете начать с первого узла, а затем непрерывно перебирать все узлы. Древовидная структура не имеет этого свойства - если вы постоянно будете переходить только по одной ссылке, вы не достигнете всех узлов в дереве.
- person templatetypedef schedule 09.02.2013
Ответы (3)
В этом более старом вопросе я дал короткий алгоритм, использующий двоичный представление числа k, чтобы найти способ выбрать k -й узел из двоичной кучи при обходе сверху вниз. Предполагая, что вы отслеживаете количество узлов в явном древовидном представлении двоичной кучи, вы можете сделать следующее, чтобы выполнить операцию вставки:
- Используя приведенный выше алгоритм, определите, куда должен идти новый узел, а затем вставьте узел в эту позицию.
- Непрерывно перемещайте узел вверх, либо перенастраивая дерево, чтобы поменять его местами с его родителем, либо обмениваясь полями данных узла и его родителя, пока элемент не займет свое окончательное положение.
Надеюсь это поможет!
person
templatetypedef
schedule
08.02.2013
Значит, если вы не знаете размер кучи, то вы не можете этим пользоваться?
- person omega; 09.02.2013
@ omega: Верно. Тем не менее, каждый из них должен отслеживать размер кучи, и это чрезвычайно полезно для производительности. Если вы не отслеживаете размер кучи, сложность вставки будет O (n), поскольку вам, возможно, придется просматривать каждый узел в дереве, чтобы определить, где находится точка вставки. Если вы отслеживаете размер, он падает до O (log n), что является огромным выигрышем в производительности.
- person templatetypedef; 09.02.2013
Какой будет алгоритм для вставки (при условии, что вы не знаете размер), который дает O (n)?
- person omega; 09.02.2013
@ omega - Вы можете выполнить BFS по дереву, упорядочивая узлы слева направо. Самый последний узел, который вы посещаете, будет либо (а) рядом с точкой вставки (если последняя строка не заполнена), либо (б) в конце строки, потому что вам нужна новая строка. Исходя из этого, вы можете найти правильную точку вставки. Или вы можете просто подсчитать количество узлов за время O (n), а затем использовать мою оригинальную технику. :-) Если серьезно, то не хранить количество узлов излишне сложно - это намного проще, чем альтернатива, и нет причин не делать этого.
- person templatetypedef; 09.02.2013
Описанный алгоритм добавляет узел в конце в log (n) + еще O (log (n)) для восходящей цепочки. Путь вставки и путь пузыря идентичны. Следовательно, вы можете вставить узел одним обходом вниз по этому пути (родительские указатели больше не нужны). Алгоритм: перейти к следующему узлу на пути, используя описанный битовый алгоритм; сравните этот узел пути с узлом вставки; если он больше, поместите узел вставки в положение узла пути и установите узел вставки = узел пути; продолжайте с (новым) узлом вставки, пока не дойдете до конца пути, и добавьте туда узел вставки. Сделанный!
- person Bartel; 05.05.2014
Если вы повесите новую вершину под любым листом вашего дерева (как левый или правый преемник, не имеет значения), а затем восстановите кучу от этой новой вершины до вершины (то есть, относительно каждой другой вершины с преемниками, поменяйте ее местами с большим преемником и, если нужно, поднимитесь вверх), ваш новый элемент найдет свое законное место, не разрушая кучу. Однако это будет гарантировать вам только то, что любая другая операция вставки займет время O (h), где h - максимальная высота дерева. Очевидно, что лучше представить кучу в виде массива, потому что таким образом гарантируется, что каждая операция вставки займет время O (logN).
person
K. Bulatov
schedule
08.02.2013
это правда, но я пытаюсь сделать это как древовидную реализацию.
- person omega; 09.02.2013
Если вы пытаетесь сделать дерево полным двоичным деревом (как это обычно бывает), то эта настройка не сработает, так как вы не будете знать, в какой лист вставлять.
- person templatetypedef; 09.02.2013
Как я уже отмечал в этом ответе, не имеет значения, какой лист вы выберете. Пока вы будете выполнять обратное восстановление после вставки каждой новой вершины, ваша куча будет согласованной. Но это будет не оптимально.
- person K. Bulatov; 09.02.2013
Если вы хотите, чтобы он был оптимальным, вы можете просто вставить новый элемент под лист, ближайший к корню. Тогда операция вставки всегда будет занимать время O (logN), потому что дерево будет самонастраивающимся.
- person K. Bulatov; 09.02.2013
Чтобы найти точное место, где должен быть вставлен новый узел, мы используем двоичное представление размера двоичной кучи. Это занимает O (log N), а затем мы всплываем, что занимает O (log N). Таким образом, операция вставки занимает O (log N) ... Для подробного объяснения ознакомьтесь с сообщением в моем блоге о двоичных кучах -
http://theoryofprogramming.com/2015/02/01/binary-heaps-and-heapsort-algorithm/
Надеюсь, это помогло вам, если это так, дайте мне знать ...! ☺
person
Vamsi Sangam
schedule
08.02.2015
