Самоорганизующаяся куча
Самоорганизующаяся куча — это представление приоритетной очереди корневым деревом, операции с которым производятся аналогично операциям с левосторонней кучей, но без использования рангов. Длина правого пути из корня такого дерева в лист может быть произвольной, поэтому время выполнения всех операций в худшем случае есть , где — число элементов в очереди. Однако среднее время выполнения произвольных операций есть , то есть время, приходящееся на одну операцию, как ни удивительно, является величиной . Для их реализации необходимо с каждым узлом дерева хранить элемент, его ключ, указатели на левое и правое поддеревья, то есть узлы представлять записями вида
Операция СЛИТЬ кучи и в одну кучу
выполняется следующим образом. Правые пути двух исходных куч
и сливаются в один путь, упорядоченный по правилам кучи, и этот путь становится левым путем результирующей кучи . Левые поддеревья узлов, попавших в результирующий левый путь, становятся правыми.
Операция ВСТАВИТЬ в кучу новый элемент производится посредством слияния кучи с кучей, содержащей единственный элемент . Таким образом, время выполнения этой операции равно времени выполнения операции СЛИТЬ.
Операция УДАЛИТЬ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ производится посредством удаления корня кучи и слияния его левой и правой подкуч. Таким образом, вычислительная сложность этой операции равна вычислительной сложности операции СЛИТЬ.
ОперацияНАЙТИ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ выполняется, очевидно, за время , так как этот элемент находится в корне.
Анализ времени выполнения операции СЛИТЬ. Поскольку время выполнения всех трудоемких операций определяется временем выполнения операции СЛИТЬ, остается проанализировать именно эту операцию. Очевидно, время ее выполнения пропорционально количеству узлов в правых путях исходных куч и . Длина такого пути в худшем случае может зависеть линейно от количества узлов в соответствующей куче. Таким образом, время выполнения операции СЛИТЬ есть величина , где , , — количества узлов в кучах , , , соответственно.
Нахождение суммарной оценки времени выполнения m операций СЛИТЬ. Введем определение. Узел назовем тяжелым, если количество узлов в его правом поддереве строго больше, чем в левом. Остальные узлы назовем легкими.
Определим потенциал коллекции куч как общее количество содержащихся в ней тяжелых узлов. Пусть — потенциал коллекции после выполнения -й операции.
Нахождение суммарной оценки времени выполнения m операций СЛИТЬ. Введем определение. Узел назовем тяжелым, если количество узлов в его правом поддереве строго больше, чем в левом. Остальные узлы назовем легкими.
Определим потенциал коллекции куч как общее количество содержащихся в ней тяжелых узлов. Пусть — потенциал коллекции после выполнения -й операции.
Утверждение.
Время выполнения операций СЛИТЬ, примененных к коллекции, состоящей из куч с нулевым потенциалом, является величиной , где
— общее количество узлов в коллекции.
Доказательство.
Пусть -я операция заключается в слиянии куч и в результирующую кучу . Пусть перед ее выполнением и — количества тяжелых узлов в правых путях куч и соответственно,
и — количества легких узлов в этих путях, ,
— количества тяжелых узлов в остальных частях куч.
Время выполнения этой операции с точностью до постоянного множителя оценивается сверху величиной .
Подсчитаем изменение потенциала при ее выполнении. Имеем
По завершении этой операции тяжелые узлы правых путей становятся легкими, их количество равно . Легкие узлы правых путей могут как стать тяжелыми, так и остаться легкими, их будет не более штук, а количества тяжелых узлов в остальной части обоих деревьев не изменились. Следовательно, количество
тяжелых узлов после выполнения операции удовлетворяет неравенству
Таким образом, получаем изменение потенциала
и, следовательно,
Из определения легкого узла следует, что количество легких узлов в куче не превосходит логарифма количества узлов в этой куче.
Следовательно, где , а — общее количество узлов в исходных кучах.
Суммируя левую и правую части последнего неравенства по , получаем, что величина
с точностью до постоянного множителя оценивается сверху величиной, пропорциональной , то есть принадлежит .
Величина является амортизационной оценкой времени выполнения операции СЛИТЬ, то есть величиной .
Замечание.
Вначале коллекция, состоящая из куч, к которым применяются операций СЛИТЬ, может иметь произвольное количество узлов, в сумме равное .Важно, чтобы потенциал каждой из них, следовательно, и суммарный потенциал был равен нулю, то есть кучи не должны первоначально иметь тяжелых узлов.
Это могут быть, например, кучи, целиком являющиеся левыми путями. Крайний случай — это куча высоты с минимальным количеством узлов, не имеющая тяжелых узлов, а также это могут быть кучи с заполненным последним уровнем узлов. Другой крайний случай — это куча высоты
с максимальным количеством узлов, не имеющая тяжелых узлов. Остальные варианты являются промежуточными.
Особое значение имеет случай, когда каждая из начальных куч состоит из единственного узла.
Итак, для всех коллекций таких куч амортизационное время выполнения одной операции СЛИТЬ является величиной , где
— общее количество их узлов.
