Нахождение последнего элемента двоичной кучи
цитируя Википедию:
Вполне допустимо использовать традиционную структуру данных двоичного дерева для реализации двоичной кучи. Существует проблема с поиском соседнего элемента на последнем уровне в двоичной куче при добавлении элемента, который может быть решен алгоритмически...
Любые идеи о том, как такой алгоритм может работать?
Мне не удалось найти какую-либо информацию об этой проблеме, поскольку большинство двоичных кучи реализованы с использованием массивов.
Любая помощь приветствуется.
Недавно я зарегистрировал учетную запись OpenID и не могу ни редактировать свое первоначальное сообщение, ни комментировать ответы. Вот почему я отвечаю через этот ответ. Извини за это.
цитируя Митча Пшеницу:
@Yse: это твой вопрос "Как мне найти последний элемент двоичной кучи"?
Да, это. Или, если быть более точным, мой вопрос: "Как найти последний элемент двоичной кучи, не основанной на массивах?".
цитирование подавления огня:
Есть ли какой-то контекст, в котором вы задаете этот вопрос? (есть ли конкретная проблема, которую вы пытаетесь решить?)
Как указано выше, я хотел бы знать хороший способ "найти последний элемент двоичной кучи, не основанной на массивах", который необходим для вставки и удаления узлов.
цитируя Роя:
Мне кажется наиболее понятным просто использовать обычную структуру двоичного дерева (используя pRoot и Node, определенные как [data, pLeftChild, pRightChild]) и добавить два дополнительных указателя (pInsertionNode и pLastNode). И pInsertionNode, и pLastNode будут обновляться во время подпрограмм вставки и удаления, чтобы они оставались актуальными при изменении данных в структуре. Это дает O(1) доступ как к точке вставки, так и к последнему узлу структуры.
Да, это должно работать. Если я не ошибаюсь, может быть немного сложно найти узел вставки и последний узел, когда их местоположение меняется на другое поддерево из-за удаления / вставки. Но я попробую.
цитируя Зака Скривена:
Как насчет выполнения поиска в глубину...
Да, это был бы хороший подход. Я тоже попробую.
Тем не менее мне интересно, есть ли способ "вычислить" местоположение последнего узла и точки вставки. Высота двоичной кучи с N узлами может быть рассчитана путем взятия логарифма (из базы 2) наименьшей степени двух, которая больше N. Возможно, также возможно рассчитать количество узлов на самом глубоком уровне. Тогда, возможно, можно было определить, как должна проходиться куча, чтобы достичь точки вставки или узла для удаления.
6 ответов
По сути, цитируемое утверждение относится к проблеме определения местоположения для вставки и удаления элементов данных в кучу и из нее. Чтобы сохранить "свойство формы" двоичной кучи, самый нижний уровень кучи всегда должен заполняться слева направо, не оставляя пустых узлов. Чтобы поддерживать среднее O(1) время вставки и удаления для двоичной кучи, вы должны быть в состоянии определить местоположение для следующей вставки и местоположение последнего узла на самом нижнем уровне, чтобы использовать для удаления корневого узла, оба в постоянное время.
Для двоичной кучи, хранящейся в массиве (с неявной, сжатой структурой данных, как объяснено в записи в Википедии), это легко. Просто вставьте новейший элемент данных в конец массива, а затем "накачайте" его на место (следуя правилам кучи). Или замените корень последним элементом в массиве "всплывающий вниз" для удаления. Для куч в массиве хранения количество элементов в куче является неявным указателем того, куда следует вставить следующий элемент данных и где найти последний элемент, который будет использоваться для удаления.
Для двоичной кучи, хранящейся в древовидной структуре, эта информация не так очевидна, но, поскольку это полное двоичное дерево, ее можно вычислить. Например, в полном двоичном дереве с 4 элементами точка вставки всегда будет правым дочерним элементом левого дочернего элемента корневого узла. Узел, который будет использоваться для удаления, всегда будет левым потомком левого потомка корневого узла. И для любого данного произвольного размера дерева, дерево всегда будет иметь определенную форму с четко определенными точками вставки и удаления. Поскольку дерево является "полным двоичным деревом" с определенной структурой для любого заданного размера, очень возможно вычислить местоположение вставки / удаления за O(1) времени. Однако подвох в том, что даже когда вы знаете, где он находится структурно, вы не знаете, где будет находиться узел в памяти. Таким образом, вы должны пройти по дереву, чтобы добраться до данного узла, который является процессом O(log n), делая все вставки и удаления минимум O(log n), нарушая обычно желаемое поведение O(1). Любой поиск ("глубина-сначала" или какой-либо другой) будет по крайней мере O(log n) также из-за отмеченной проблемы обхода и обычно O(n) из-за случайного характера полусортированной кучи.
Хитрость заключается в том, чтобы иметь возможность рассчитывать и ссылаться на эти точки вставки / удаления в постоянное время либо путем увеличения структуры данных ("потоковая обработка" дерева, как упомянуто в статье в Википедии), либо с помощью дополнительных указателей.
Реализация, которая кажется мне наиболее простой для понимания, с малым объемом памяти и дополнительными затратами на кодирование, состоит в том, чтобы просто использовать обычную простую структуру двоичного дерева (используя pRoot и Node, определенные как [data, pParent, pLeftChild, pRightChild]) и добавить два дополнительных указателя (pInsert и pLastNode). pInsert и pLastNode будут обновляться во время подпрограмм вставки и удаления, чтобы поддерживать их актуальность при изменении данных в структуре. Эта реализация дает O(1) доступ как к точке вставки, так и к последнему узлу структуры и должна обеспечивать сохранение общего поведения O(1) как при вставке, так и при удалении. Стоимость реализации составляет два дополнительных указателя и некоторый незначительный дополнительный код в подпрограммах вставки / удаления (иначе, минимальный).
РЕДАКТИРОВАТЬ: добавлен псевдокод для вставки O(1) ()
Вот псевдокод для подпрограммы вставки, который в среднем равен O(1):
define Node = [T data, *pParent, *pLeft, *pRight]
void insert(T data)
{
do_insertion( data ); // do insertion, update count of data items in tree
# assume: pInsert points node location of the tree that where insertion just took place
# (aka, either shuffle only data during the insertion or keep pInsert updated during the bubble process)
int N = this->CountOfDataItems + 1; # note: CountOfDataItems will always be > 0 (and pRoot != null) after an insertion
p = new Node( <null>, null, null, null); // new empty node for the next insertion
# update pInsert (three cases to handle)
if ( int(log2(N)) == log2(N) )
{# #1 - N is an exact power of two
# O(log2(N))
# tree is currently a full complete binary tree ("perfect")
# ... must start a new lower level
# traverse from pRoot down tree thru each pLeft until empty pLeft is found for insertion
pInsert = pRoot;
while (pInsert->pLeft != null) { pInsert = pInsert->pLeft; } # log2(N) iterations
p->pParent = pInsert;
pInsert->pLeft = p;
}
else if ( isEven(N) )
{# #2 - N is even (and NOT a power of 2)
# O(1)
p->pParent = pInsert->pParent;
pInsert->pParent->pRight = p;
}
else
{# #3 - N is odd
# O(1)
p->pParent = pInsert->pParent->pParent->pRight;
pInsert->pParent->pParent->pRight->pLeft = p;
}
pInsert = p;
// update pLastNode
// ... [similar process]
}
Таким образом, вставка (T) в среднем равна O(1): точно O(1) во всех случаях, кроме случаев, когда дерево должно быть увеличено на один уровень, когда оно равно O(log N), что происходит при каждом добавлении журнала N (при условии, что нет делеции). Добавление другого указателя (pLeftmostLeaf) может сделать insert() O(1) для всех случаев и избежать возможного патологического случая чередующейся вставки и удаления в полностью полном двоичном дереве. (Добавление pLeftmost оставлено в качестве упражнения [это довольно легко].)
Я впервые участвовал в переполнении стека.
Да, приведенный выше ответ Зака Скривены (боже, я не знаю, как правильно обращаться с другими людьми, извините) является правильным. Я хочу добавить упрощенный способ, если нам дается количество узлов.
Основная идея:
Учитывая количество N узлов в этом полном двоичном дереве, выполните вычисление "N % 2" и поместите результаты в стек. Продолжайте расчет до N == 1. Затем выведите результаты. Результат равен 1 означает право, 0 означает слева. Последовательность - это путь от корня до целевой позиции.
Пример:
Теперь в дереве 10 узлов, я хочу вставить еще один узел в позицию 11. Как его направить?
11 % 2 = 1 --> right (the quotient is 5, and push right into stack)
5 % 2 = 1 --> right (the quotient is 2, and push right into stack)
2 % 2 = 0 --> left (the quotient is 1, and push left into stack. End)
Затем вытолкните стек: влево -> вправо -> вправо. Это путь от корня.
Вы можете использовать двоичное представление размера двоичной кучи, чтобы найти местоположение последнего узла в O(log N). Размер может быть сохранен и увеличен, что займет O(1) время. Основополагающим понятием этого является структура двоичного дерева.
Предположим, что наш размер кучи равен 7. Бинарное представление 7 - "111". Теперь не забывайте всегда опускать первый бит. Итак, теперь мы остались с "11". Читайте слева направо. Бит равен 1, поэтому перейдите к правому дочернему элементу корневого узла. Тогда оставленная строка - "1", первый бит - "1". Итак, снова перейдите к правому потомку текущего узла, в котором вы находитесь. Поскольку у вас больше нет битов для обработки, это означает, что вы достигли последнего узла. Итак, необработанная работа процесса заключается в том, что преобразуйте размер кучи в биты. Опустить первый бит. В соответствии с крайним левым битом перейдите к правому дочернему элементу текущего узла, если он равен "1", и к левому дочернему элементу текущего узла, если он равен "0".
Как всегда, до самого конца двоичного дерева эта операция всегда занимает O (log N) времени. Это простая и точная процедура поиска последнего узла.
Вы можете не понять это в первом чтении. Попробуйте применить этот метод на бумаге для различных значений Binary Heap, я уверен, что вы поймете, что за этим стоит интуиция. Я уверен, что этих знаний достаточно, чтобы решить вашу проблему, если вы хотите больше объяснений с цифрами, вы можете обратиться к моему блогу.
Надеюсь, мой ответ помог вам, если да, дайте мне знать...! ☺
Как насчет выполнения поиска в глубину, посещение левого ребенка перед правым ребенком, чтобы определить высоту дерева. После этого первый лист, с которым вы столкнетесь с более короткой глубиной, или родитель с отсутствующим дочерним элементом будет указывать, куда вы должны поместить новый узел, прежде чем "всплыть".
Приведенный выше подход поиска в глубину (DFS) не предполагает, что вы знаете общее количество узлов в дереве. Если эта информация доступна, то мы можем быстро увеличить масштаб до нужного места, используя свойства полных двоичных деревьев:
Пусть N - общее количество узлов в дереве, а H - высота дерева.
Некоторые значения (N, H): (1,0), (2,1), (3,1), (4,2), ..., (7,2), (8, 3). Общая формула, связывающая эти два: H = ceil [log2 (N +1)] - 1. Теперь, учитывая только N, мы хотим перейти от корня к позиции для нового узла, за наименьшее количество шагов, т.е. без какого-либо "возврата". Сначала мы вычисляем общее количество узлов M в идеальном бинарном дереве высотой H = ceil [log2 (N +1)] - 1, которое равно M = 2 ^ (H +1) - 1.
Если N == M, то наше дерево идеально, и новый узел должен быть добавлен на новом уровне. Это означает, что мы можем просто выполнить DFS (слева направо), пока не достигнем первого листа; новый узел становится левым потомком этого листа. Конец истории.
Однако, если N < M, то на последнем уровне нашего дерева все еще есть вакансии, и новый узел должен быть добавлен в крайнее левое свободное место. Количество узлов, которые уже находятся на последнем уровне нашего дерева, просто (N - 2 ^ H + 1). Это означает, что новый узел занимает точку X = (N - 2 ^ H + 2) слева на последнем уровне.
Теперь, чтобы добраться туда от корня, вам нужно будет делать правильные повороты (L против R) на каждом уровне, чтобы вы оказались в точке X на последнем уровне. На практике вы будете определять ходы с небольшими вычислениями на каждом уровне. Тем не менее, я думаю, что в следующей таблице показана общая картина и соответствующие шаблоны без арифметики (вы можете распознать это как форму арифметического кодирования для равномерного распределения):
0 0 0 0 0 X 0 0 <--- represents the last level in our tree, X marks the spot!
^
L L L L R R R R <--- at level 0, proceed to the R child
L L R R L L R R <--- at level 1, proceed to the L child
L R L R L R L R <--- at level 2, proceed to the R child
^ (which is the position of the new node)
this column tells us
if we should proceed to the L or R child at each level
РЕДАКТИРОВАТЬ: Добавлено описание того, как добраться до нового узла в кратчайшее количество шагов, предполагая, что мы знаем общее количество узлов в дереве.
Решение, если у вас нет ссылки на родителя!!! Чтобы найти правильное место для следующего узла, вам нужно обработать 3 случая
- case (1) Уровень дерева завершен Log2 (N)
- case (2) Количество узлов дерева четное
- case (3) Количество узлов дерева нечетно
Вставка:
void Insert(Node root,Node n)
{
Node parent = findRequiredParentToInsertNewNode (root);
if(parent.left == null)
parent.left = n;
else
parent.right = n;
}
Найдите родителя узла, чтобы вставить его
void findRequiredParentToInsertNewNode(Node root){
Node last = findLastNode(root);
//Case 1
if(2*Math.Pow(levelNumber) == NodeCount){
while(root.left != null)
root=root.left;
return root;
}
//Case 2
else if(Even(N)){
Node n =findParentOfLastNode(root ,findParentOfLastNode(root ,last));
return n.right;
}
//Case 3
else if(Odd(N)){
Node n =findParentOfLastNode(root ,last);
return n;
}
}
Чтобы найти последний узел, вам нужно выполнить BFS (поиск в ширину) и получить последний элемент в очереди.
Node findLastNode(Node root)
{
if (root.left == nil)
return root
Queue q = new Queue();
q.enqueue(root);
Node n = null;
while(!q.isEmpty()){
n = q.dequeue();
if ( n.left != null )
q.enqueue(n.left);
if ( n.right != null )
q.enqueue(n.right);
}
return n;
}
Найдите родителя последнего узла, чтобы установить узел на ноль в случае замены на корень в случае удаления
Node findParentOfLastNode(Node root ,Node lastNode)
{
if(root == null)
return root;
if( root.left == lastNode || root.right == lastNode )
return root;
Node n1= findParentOfLastNode(root.left,lastNode);
Node n2= findParentOfLastNode(root.left,lastNode);
return n1 != null ? n1 : n2;
}
Я знаю, что это старая тема, но я искал ответ на тот же вопрос. Но я не мог позволить себе решение o(log n), так как мне пришлось искать последний узел тысячи раз за несколько секунд. У меня был алгоритм O(log n), но моя программа сканировала из-за того, сколько раз она выполняла эту операцию. Так что после долгих раздумий я наконец нашел решение для этого. Не уверен, что если кому-то это интересно.
Это решение O(1) для поиска. Для вставки это определенно меньше, чем O(log n), хотя я не могу сказать, что это O(1).
Просто хотел добавить, что, если есть интерес, я также могу предоставить свое решение. Решение состоит в том, чтобы добавить узлы в двоичной куче в очередь. Каждый узел очереди имеет передний и задний указатели. Мы продолжаем добавлять узлы в конец этой очереди слева направо, пока не достигнем последнего узла в двоичной куче. В этот момент последний узел в двоичной куче будет находиться в задней части очереди. Каждый раз, когда нам нужно найти последний узел, мы снимаем очередь с задней стороны, и теперь второй-последний становится последним узлом в дереве. Когда мы хотим вставить, мы ищем сзади сзади первый узел, куда мы можем вставить и поместить его туда. Это не совсем O(1), но значительно сокращает время работы.