В сущности, цитируемое утверждение относится к проблеме определения местоположения для вставки и удаления элементов данных в кучу и из нее. Чтобы поддерживать «свойство формы» двоичной кучи, самый нижний уровень кучи всегда должен заполняться слева направо, не оставляя пустых узлов. Чтобы поддерживать среднее 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 оставлено в качестве упражнения [это довольно легко].)