Структуры данных и модели вычислений

Тонкие кучи

Разбить на страницы
Показывать лекцию целиком

Рассматриваемые здесь тонкие и, в следующей лекции, толстые кучи предложены М.Фредманом и Х.Капланом как альтернатива фибоначчиевым кучам. Долгое время фибоначчиевы кучи считались рекордными по производительности. Оценки операций над фибоначчиевыми кучами имеют амортизационный характер, а скрытые в них константы велики настолько, что реальный выигрыш во времени работы с ними достигался только на данных "астрономических" размеров. Рассматриваемые здесь тонкие кучи имеют те же асимптотические оценки, что и фибоначчиевы, но гораздо практичнее их. Оценки для толстых куч "хуже" по операции слияния, выполняемой за O(\log n) времени. Достоинством этой структуры является то, что ее оценки рассчитаны на худший случай. Заметим, что на данный момент ни фибоначчиевы, ни толстые, ни тонкие кучи не являются рекордными, так как Г.Бродал предложил новую структуру, которую мы будем называть кучей Бродала. Кучи Бродала характеризуется такими же, как и фибоначчиевы кучи, оценками операций, но все оценки справедливы для худшего случая. К сожалению, структура, предложенная Г.Бродалом, сложна для реализации. Рассмотрим реализацию приоритетной очереди с помощью тонкой кучи.

Основные определения

Тонкие кучи, как и многие другие кучеобразные структуры, аналогичны биномиальным кучам.

Тонкое дерево $$T_k$$ ранга $$k$$ — это дерево, которое может быть получено из биномиального дерева $$B_k$$ удалением у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына. Заметим, что у листьев детей нет, а если у корня $$B_k$$ удалить самого левого сына, то $$B_k$$ превратится в $$B_{k-1}$$. Ранг тонкого дерева равен количеству детей корня.

Для любого узла $$x$$ в дереве $$T_k$$ обозначим: $${\rm Degree} (x)$$ — количество детей узла $$x$$ ; $${\rm Rank}(x)$$ — ранг соответствующего узла в биномиальном дереве $$B_k$$.

Тонкое дерево $$T_k$$ удовлетворяет следующим условиям:

  • Для любого узла $$x$$ либо $${\rm Degree} (x) = {\rm Rank}(x)$$, в этом случае говорим, что узел $$x$$ не помечен (полный); либо $${\rm Degree} (x) = {\rm Rank}(x) - 1$$, в этом случае говорим, что узел $$x$$ помечен (неполный).
  • Корень не помечен (полный).
  • Для любого узла $$x$$ ранги его детей от самого правого к самому левому равны соответственно $$0, 1, 2\dts {\rm Degree}(x) - 1$$.
  • Узел $$x$$ помечен тогда и только тогда, если его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1 и он не имеет детей.
    •

    На рис. 8.1 приведены примеры тонких деревьев; числа рядом с узлами обозначают их ранги. Вверху изображено биномиальное дерево $$B_3$$, внизу — два полученных из $$B_3$$ тонких дерева ранга три. Стрелки указывают на помеченные узлы. Заметим, что биномиальное дерево является тонким деревом, у которого все узлы не помечены.

    Тонкий лес — это набор тонких деревьев, ранги которых не обязательно попарно различны.

    (рис 8.1)

    Тонкая куча — это кучеобразно нагруженный тонкий лес.

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

    Утверждение. Для любого натурального числа $$n$$ существует тонкий лес, который содержит ровно $$n$$ элементов и состоит из тонких деревьев попарно различных рангов.

    Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо.

    Пусть $$D(n)$$ — максимально возможный ранг узла в тонкой куче, содержащей $$n$$ элементов.

    Теорема [22] В тонкой куче из $$n$$ элементов $$D(n)\le \log_\Phi (n)$$, где $$\Phi = (1+\sqrt{5})/2$$ — золотое сечение.

    Доказательство. Сначала покажем, что узел ранга $$k$$ в тонком дереве имеет не менее $$F_k \ge \Phi^{k-1}$$ потомков, включая самого себя, где $$F_k$$ — $$k$$ -е число Фибоначчи, определяемое соотношениями $$F_0 = 1$$, $$F_1 = 1$$, $$F_k = F_{k-2} + F_{k-1}$$ для $$k \ge 2$$.

    Действительно, пусть $$T_k$$ — минимально возможное число узлов, включая самого себя, в тонком дереве ранга $$k$$. По свойствам $$1$$ и $$3$$ тонкого дерева получаем следующие соотношения:$$\eq*{ T_0 = 1,\ T_1 = 1,\ T_{k} \ge 1+\suml_{i=0}^{k-2} T_{i}\q \t{для}\quad k \ge 2. }$$

    Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что $$T_k \ge F_k$$ для любых $$k$$. Неравенство $$F_k \ge \Phi^{k-1}$$ хорошо известно.

    Теперь убедимся в том, что максимально возможный ранг $$D(n)$$ тонкого дерева в тонкой куче, содержащей $$n$$ элементов, не превосходит числа $$\log_{\Phi }(n)+1$$. Действительно, выберем в тонкой куче дерево максимального ранга. Пусть $$n^\ast$$ — количество вершин в этом дереве, тогда $${n \ge n^\ast \ge \Phi^{D(n)-1}}$$.

    Отсюда следует, что $$D(n) \le \log_{\Phi}(n)+1$$.

    Представление тонкой кучи в памяти компьютера.

    Тонкие кучи формируют из узлов, представленных записями следующего вида:$$\eq*{ {\rm Node} = ({\rm Key}, {\rm Left}, {\rm Right}, {\rm LChild}, {\rm Rank}), }$$ где $${\rm Key}$$ — ключ элемента, приписанного узлу; $${\rm Left}$$ — указатель на ближайшего левого брата, если такового нет, то на родителя, а если нет и родителя, то указатель заземлен; $${\rm Right}$$ — указатель на ближайшего правого брата, если такового нет, то указатель заземлен; $${\rm LChild}$$ — указатель на самого левого сына, если такового нет, то указатель заземлен; $${\rm Rank}$$ — ранг узла.

    Таким образом, узлы-братья связаны в двусвязный список при помощи указателей $${\rm Left}$$ и $${\rm Right}$$. У самого левого брата в этом списке указатель $${\rm Left}$$ указывает на общего родителя всех узлов в списке. У самого правого брата из списка указатель $${\rm Right}$$ заземлен. Корни деревьев в тонкой куче связаны в односвязный циклический список. Этот список будем называть корневым списком. Корневой список реализуется при помощи поля $${\rm Right}$$. Поле $${\rm Left}$$ у каждого узла корневого списка заземлено.

    В случае необходимости в описании узла может присутствовать и другая прикладная информация. На рис. 8.2 приведен пример тонкой кучи.

    Представление кучи со ссылками, в узлах указаны ранги

    (рис 8.2)

    Заметим, что принадлежность заданного узла корневому списку кучи осуществляется проверкой указателя $${\rm Left}$$ на заземленность.

    Введем еще одну запись $${\rm Heap}$$, которая будет соответствовать отдельной куче и иметь вид$$\eq*{ {\rm Heap} = ({\rm First}, {\rm Min}), }$$ где $${\rm First}$$ — указатель на начальный элемент корневого списка; $${\rm Min}$$ — указатель на элемент корневого списка с минимальным ключом.

    Очевидно, что узел с минимальным ключом обязательно находится в корневом списке.

    Реализация основных операций и оценки трудоемкости

    Сосредоточим внимание на амортизационных оценках трудоемкости. Будем получать их методом потенциалов. Потенциалом тонкой кучи будем считать величину $$\Phi = n + 2\cdot m$$, где $$n$$ — количество деревьев в куче, а $$m$$ — число помеченных вершин. Заметим, что потенциал кучи неотрицателен и в начальный момент равен $$0$$.

    Операция MakeHeap. Эта операция создает указатель на новую пустую кучу. Очевидно, фактическая стоимость операции есть $$O(1)$$, а потенциал созданной кучи равен $$0$$.

    Операция FindMin (H). Указатель на узел с минимальным ключом в куче $$H$$ определяется с помощью указателя $${\rm Min}$$. Если куча пуста, то результирующий указатель нулевой. Амортизационная оценка совпадает с фактической и равна $$O(1)$$, потенциал не изменяется.

    Операция Insert(i,H). С помощью этой операции осуществляется вставка в кучу $$H$$ нового элемента с ключом $$i$$. При ее реализации создается новое тонкое дерево ранга $$0$$, которое вставляется в корневой список кучи $$H$$, разрывая его в произвольном месте. При необходимости перевычисляется ссылка на минимальный элемент.

    Операция увеличивает потенциал на $$1$$, так как добавляется одно дерево в корневой список кучи, но это не влияет на амортизационную оценку, которая равна фактической $$O(1)$$.

    Операция Meld(H1, H2). Результатом этой операции является указатель на кучу, полученную слиянием двух куч $$H_1$$ и $$H_2$$. Она осуществляется соединением корневых списков сливаемых куч. При таком способе выполнения операции, как и при реализации вставки элемента в кучу, можем получить в корневом списке результирующей кучи несколько деревьев одинакового ранга. При удобном случае, а именно при удалении минимального элемента, мы освободим корневой список от этой неоднозначности. Оценка совпадает с оценками для всех предыдущих операций. Суммарный потенциал не изменяется.

    Операция DeleteMin(H). Эта операция предназначена для удаления узла с минимальным ключом из непустой кучи $$H$$. Для ее реализации удаляем минимальный узел из корневого списка кучи $$H$$, добавляем список детей удаленного узла в корневой список и повторяем следующий "связывающий шаг".

    Находим любые два дерева, корни которых имеют одинаковые ранги, и связываем их, делая корень с большим ключом новым левым потомком корня с меньшим ключом, увеличивая ранг нового полученного тонкого дерева на единицу. При этом следует удалить из корневого списка кучи $$H$$ корень с большим ключом. Как только не останется деревьев с корнями одинакового ранга, в полученном корневом списке необходимо найти элемент с минимальным ключом.

    Рассмотрим теперь, с помощью каких средств реализуется связывающий шаг. Для хранения ссылок на корни деревьев используем временный массив $${\rm RankT}$$, размера $$D(n)$$. Величина $${\rm RankT}[i]$$ будет указателем на тонкое дерево ранга $$i$$. Если найдется еще одно дерево ранга $$i$$, то свяжем два дерева ранга $$i$$ в одно дерево ранга $$i + 1$$, в $$i$$ -й ячейке массива $${\rm RankT}$$ установим нулевой указатель и продолжим связывающую процедуру с вновь полученным деревом ранга $$i + 1$$.

    При включении списка детей необходимо учесть возможность помеченности детей минимального узла. То есть уменьшить их ранг там, где это необходимо. Это требование вытекает из свойства 2 определения тонкого дерева. Очевидно, что для проверки помеченности узла требуется $$O(1)$$ операций.

    В результате выполнения связывающих шагов получаем заполненный массив $${\rm RankT}$$. Теперь остается только связать все деревья, находящиеся в этом массиве, в корневой список и найти в этом списке новый минимальный элемент. Очевидно, все это можно выполнить с трудоемкостью $$O(D(n))$$.

    Чтобы оценить амортизационную стоимость операции $${\rm DeleteMin}$$, подсчитаем фактическую стоимость операции и изменение потенциала. Фактическая стоимость складывается из $$O(1)$$ операций на проверку кучи на пустоту, $$O(D(n))$$ действий при добавлении детей минимального узла в корневой список и $$O$$ (количество связывающих шагов) + $$O(D(n))$$ при выполнении связывающих шагов.

    В итоге фактическая стоимость операции удаления минимального элемента есть $$O$$ (количество связывающих шагов) + $$D(n)$$.

    Очевидно, что потенциал уменьшился, как минимум, на число связывающих шагов, так как при каждом связывающем шаге количество деревьев в корневом списке уменьшается на единицу. Поскольку амортизационная стоимость равна фактической стоимости плюс изменение потенциала, то амортизационная стоимость равна $$O(D(n))$$.

    Операция DecreaseKey $$(\Dl, i, H).$$ При уменьшении ключа у некорневого элемента $$i$$ в куче $$H$$ на величину $$\Dl$$ может быть нарушено свойство кучеобразности. Для восстановления этого свойства перемещаем поддерево с корнем в изменяемом элементе в корневой список, но при этом, возможно, оставшееся после переноса дерево может не оказаться тонким.

    Покажем, как, затратив $$O(1)$$ амортизированного времени, исправлять его структуру. В процедуре $${\rm DecreaseKey}$$ после уменьшения ключа корректируется, если это необходимо, указатель на минимальный элемент кучи. После этого проверяется, не является ли измененный узел $$x$$ корнем дерева $$T$$. Если это действительно так, то процедура завершается, в противном случае переносим поддерево с корнем в узле $$x$$ в корневой список кучи и запускаем процедуру коррекции оставшегося дерева $$T'$$.

    Будем различать два вида нарушений свойств тонкого дерева:

  • Братские нарушения — это нарушения третьего правила из определения тонкого дерева.
  • Родительские нарушения — это нарушения первого или второго правила.
    •

    Рассмотрим подробнее каждое из двух видов нарушений. Назовем узел $$y$$ узлом локализации братского нарушения среди детей узла $$z$$, если ранг узла $$y$$ отличается от ранга его ближайшего правого брата на 2, либо он не имеет правого брата и его ранг равен 1. Пример — на рис. 8.3.

    (рис 8.3)

    Назовем узел $$y$$ узлом локализации родительского нарушения, если выполнено одно из трех условий:

  • Ранг узла $$y$$ на три больше, чем ранг его самого левого сына.
  • Ранг узла $$y$$ равен двум, и он не имеет детей.
  • Узел $$y$$ есть помеченный корень дерева.
    •

    Пример приведен на рис. 8.4.

    (рис 8.4)

    Рассмотрим теперь, как можно перестроить дерево, чтобы избавиться от братского нарушения либо свести его к родительскому. Пусть узел $$y$$ — это узел локализации братского нарушения. Рассмотрим два возможных варианта.

    Узел $$y$$ не помечен, то есть ранг его самого левого сына на единицу меньше ранга самого узла $$y$$. Пример — на рис. 8.5.

    (рис 8.5)

    В данном случае, чтобы исправить братское нарушение, помещаем на место пропущенного в братском списке поддерева поддерево с корнем в самом левом сыне узла $$y$$. Узел $$y$$ при такой операции становится помеченным, но зато дерево теперь удовлетворяет всем трем свойствам определения тонкого дерева. Очевидно, что это операция заканчивает процедуру исправления дерева.

    Узел $$y$$ помечен, тогда уменьшаем ранг узла $$y$$ на единицу. Это не исправит дерева, но зато теперь узлом локализации нарушения будет левый брат узла $$y$$ либо его родитель. В последней ситуации нарушение становится родительским. Пример приведен на рис. 8.6.

    (рис 8.6)

    Таким образом, мы либо исправим структуру дерева, либо рекурсивно придем к узлу локализации родительского нарушения.

    Выясним, чтo же делать с родительскими нарушениями. Пусть узел $$y$$ — это узел локализации родительского нарушения, а узел $$z$$ — родитель узла $$y$$. Тогда предлагается переместить поддерево с корнем в узле $$y$$ в корневой список кучи, делая при этом узел $$y$$ непомеченным. Считаем, что $$z$$ — это не корень дерева. Если узел $$z$$ не был помечен, то, очевидно, процедура исправления дерева закончена. Если он был помечен, то считаем его узлом локализации нового родительского нарушения. При этом, очевидно, количество помеченных узлов уменьшится на единицу. Продолжая такого вида рекурсивные шаги, мы либо дойдем до корня дерева, либо исправим его структуру раньше. Если узел $$z$$ стал корнем, то для того чтобы исправить структуру дерева, необходимо лишь сделать ранг корня на единицу большим ранга его самого левого сына. На этом процедура исправления дерева будет закончена.

    Заметим, что каждый промежуточный шаг рекурсии уменьшает число помеченных узлов на единицу и добавляет в корневой список не более одного дерева. Тогда потенциал при каждом шаге рекурсии уменьшается как минимум на единицу. Отсюда и следует обещанная оценка $$O(1)$$ времени выполнения операции $${\rm DecreaseKey}$$.

    Операция Delete(i,H) удаляет элемент $$i$$ из кучи $$H$$ следующим образом. Ключ удаляемого элемента $$i$$ уменьшается до некоторого значения, меньше минимального, и элемент удаляется как минимальный. Очевидно, что трудоемкость этой операции есть $$O(D(n))$$.

    Итак, амортизационная трудоемкость выполнения операций\linebreak $${\rm DeleteMin}$$ и $${\rm Delete}$$ на тонкой куче из $$n$$ элементов равна $$O(\log n)$$, а для остальных операций, как было показано ранее, — $$O(1)$$.

    Страницы:

    Рассматриваемые здесь тонкие и, в следующей лекции, толстые кучи предложены М.Фредманом и Х.Капланом как альтернатива фибоначчиевым кучам. Долгое время фибоначчиевы кучи считались рекордными по производительности. Оценки операций над фибоначчиевыми кучами имеют амортизационный характер, а скрытые в них константы велики настолько, что реальный выигрыш во времени работы с ними достигался только на данных "астрономических" размеров. Рассматриваемые здесь тонкие кучи имеют те же асимптотические оценки, что и фибоначчиевы, но гораздо практичнее их. Оценки для толстых куч "хуже" по операции слияния, выполняемой за O(\log n) времени. Достоинством этой структуры является то, что ее оценки рассчитаны на худший случай. Заметим, что на данный момент ни фибоначчиевы, ни толстые, ни тонкие кучи не являются рекордными, так как Г.Бродал предложил новую структуру, которую мы будем называть кучей Бродала. Кучи Бродала характеризуется такими же, как и фибоначчиевы кучи, оценками операций, но все оценки справедливы для худшего случая. К сожалению, структура, предложенная Г.Бродалом, сложна для реализации. Рассмотрим реализацию приоритетной очереди с помощью тонкой кучи.

    Основные определения

    Тонкие кучи, как и многие другие кучеобразные структуры, аналогичны биномиальным кучам.

    Тонкое дерево $$T_k$$ ранга $$k$$ — это дерево, которое может быть получено из биномиального дерева $$B_k$$ удалением у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына. Заметим, что у листьев детей нет, а если у корня $$B_k$$ удалить самого левого сына, то $$B_k$$ превратится в $$B_{k-1}$$. Ранг тонкого дерева равен количеству детей корня.

    Для любого узла $$x$$ в дереве $$T_k$$ обозначим: $${\rm Degree} (x)$$ — количество детей узла $$x$$ ; $${\rm Rank}(x)$$ — ранг соответствующего узла в биномиальном дереве $$B_k$$.

    Тонкое дерево $$T_k$$ удовлетворяет следующим условиям:

  • Для любого узла $$x$$ либо $${\rm Degree} (x) = {\rm Rank}(x)$$, в этом случае говорим, что узел $$x$$ не помечен (полный); либо $${\rm Degree} (x) = {\rm Rank}(x) - 1$$, в этом случае говорим, что узел $$x$$ помечен (неполный).
  • Корень не помечен (полный).
  • Для любого узла $$x$$ ранги его детей от самого правого к самому левому равны соответственно $$0, 1, 2\dts {\rm Degree}(x) - 1$$.
  • Узел $$x$$ помечен тогда и только тогда, если его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1 и он не имеет детей.
    •

    На рис. 8.1 приведены примеры тонких деревьев; числа рядом с узлами обозначают их ранги. Вверху изображено биномиальное дерево $$B_3$$, внизу — два полученных из $$B_3$$ тонких дерева ранга три. Стрелки указывают на помеченные узлы. Заметим, что биномиальное дерево является тонким деревом, у которого все узлы не помечены.

    Тонкий лес — это набор тонких деревьев, ранги которых не обязательно попарно различны.

    (рис 8.1)

    Тонкая куча — это кучеобразно нагруженный тонкий лес.

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

    Утверждение. Для любого натурального числа $$n$$ существует тонкий лес, который содержит ровно $$n$$ элементов и состоит из тонких деревьев попарно различных рангов.

    Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо.

    Пусть $$D(n)$$ — максимально возможный ранг узла в тонкой куче, содержащей $$n$$ элементов.

    Теорема [22] В тонкой куче из $$n$$ элементов $$D(n)\le \log_\Phi (n)$$, где $$\Phi = (1+\sqrt{5})/2$$ — золотое сечение.

    Доказательство. Сначала покажем, что узел ранга $$k$$ в тонком дереве имеет не менее $$F_k \ge \Phi^{k-1}$$ потомков, включая самого себя, где $$F_k$$ — $$k$$ -е число Фибоначчи, определяемое соотношениями $$F_0 = 1$$, $$F_1 = 1$$, $$F_k = F_{k-2} + F_{k-1}$$ для $$k \ge 2$$.

    Действительно, пусть $$T_k$$ — минимально возможное число узлов, включая самого себя, в тонком дереве ранга $$k$$. По свойствам $$1$$ и $$3$$ тонкого дерева получаем следующие соотношения:$$\eq*{ T_0 = 1,\ T_1 = 1,\ T_{k} \ge 1+\suml_{i=0}^{k-2} T_{i}\q \t{для}\quad k \ge 2. }$$

    Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что $$T_k \ge F_k$$ для любых $$k$$. Неравенство $$F_k \ge \Phi^{k-1}$$ хорошо известно.

    Теперь убедимся в том, что максимально возможный ранг $$D(n)$$ тонкого дерева в тонкой куче, содержащей $$n$$ элементов, не превосходит числа $$\log_{\Phi }(n)+1$$. Действительно, выберем в тонкой куче дерево максимального ранга. Пусть $$n^\ast$$ — количество вершин в этом дереве, тогда $${n \ge n^\ast \ge \Phi^{D(n)-1}}$$.

    Отсюда следует, что $$D(n) \le \log_{\Phi}(n)+1$$.

    Представление тонкой кучи в памяти компьютера.

    Тонкие кучи формируют из узлов, представленных записями следующего вида:$$\eq*{ {\rm Node} = ({\rm Key}, {\rm Left}, {\rm Right}, {\rm LChild}, {\rm Rank}), }$$ где $${\rm Key}$$ — ключ элемента, приписанного узлу; $${\rm Left}$$ — указатель на ближайшего левого брата, если такового нет, то на родителя, а если нет и родителя, то указатель заземлен; $${\rm Right}$$ — указатель на ближайшего правого брата, если такового нет, то указатель заземлен; $${\rm LChild}$$ — указатель на самого левого сына, если такового нет, то указатель заземлен; $${\rm Rank}$$ — ранг узла.

    Таким образом, узлы-братья связаны в двусвязный список при помощи указателей $${\rm Left}$$ и $${\rm Right}$$. У самого левого брата в этом списке указатель $${\rm Left}$$ указывает на общего родителя всех узлов в списке. У самого правого брата из списка указатель $${\rm Right}$$ заземлен. Корни деревьев в тонкой куче связаны в односвязный циклический список. Этот список будем называть корневым списком. Корневой список реализуется при помощи поля $${\rm Right}$$. Поле $${\rm Left}$$ у каждого узла корневого списка заземлено.

    В случае необходимости в описании узла может присутствовать и другая прикладная информация. На рис. 8.2 приведен пример тонкой кучи.

    Представление кучи со ссылками, в узлах указаны ранги

    (рис 8.2)

    Заметим, что принадлежность заданного узла корневому списку кучи осуществляется проверкой указателя $${\rm Left}$$ на заземленность.

    Введем еще одну запись $${\rm Heap}$$, которая будет соответствовать отдельной куче и иметь вид$$\eq*{ {\rm Heap} = ({\rm First}, {\rm Min}), }$$ где $${\rm First}$$ — указатель на начальный элемент корневого списка; $${\rm Min}$$ — указатель на элемент корневого списка с минимальным ключом.

    Очевидно, что узел с минимальным ключом обязательно находится в корневом списке.

    Реализация основных операций и оценки трудоемкости

    Сосредоточим внимание на амортизационных оценках трудоемкости. Будем получать их методом потенциалов. Потенциалом тонкой кучи будем считать величину $$\Phi = n + 2\cdot m$$, где $$n$$ — количество деревьев в куче, а $$m$$ — число помеченных вершин. Заметим, что потенциал кучи неотрицателен и в начальный момент равен $$0$$.

    Операция MakeHeap. Эта операция создает указатель на новую пустую кучу. Очевидно, фактическая стоимость операции есть $$O(1)$$, а потенциал созданной кучи равен $$0$$.

    Операция FindMin (H). Указатель на узел с минимальным ключом в куче $$H$$ определяется с помощью указателя $${\rm Min}$$. Если куча пуста, то результирующий указатель нулевой. Амортизационная оценка совпадает с фактической и равна $$O(1)$$, потенциал не изменяется.

    Операция Insert(i,H). С помощью этой операции осуществляется вставка в кучу $$H$$ нового элемента с ключом $$i$$. При ее реализации создается новое тонкое дерево ранга $$0$$, которое вставляется в корневой список кучи $$H$$, разрывая его в произвольном месте. При необходимости перевычисляется ссылка на минимальный элемент.

    Операция увеличивает потенциал на $$1$$, так как добавляется одно дерево в корневой список кучи, но это не влияет на амортизационную оценку, которая равна фактической $$O(1)$$.

    Операция Meld(H1, H2). Результатом этой операции является указатель на кучу, полученную слиянием двух куч $$H_1$$ и $$H_2$$. Она осуществляется соединением корневых списков сливаемых куч. При таком способе выполнения операции, как и при реализации вставки элемента в кучу, можем получить в корневом списке результирующей кучи несколько деревьев одинакового ранга. При удобном случае, а именно при удалении минимального элемента, мы освободим корневой список от этой неоднозначности. Оценка совпадает с оценками для всех предыдущих операций. Суммарный потенциал не изменяется.

    Операция DeleteMin(H). Эта операция предназначена для удаления узла с минимальным ключом из непустой кучи $$H$$. Для ее реализации удаляем минимальный узел из корневого списка кучи $$H$$, добавляем список детей удаленного узла в корневой список и повторяем следующий "связывающий шаг".

    Находим любые два дерева, корни которых имеют одинаковые ранги, и связываем их, делая корень с большим ключом новым левым потомком корня с меньшим ключом, увеличивая ранг нового полученного тонкого дерева на единицу. При этом следует удалить из корневого списка кучи $$H$$ корень с большим ключом. Как только не останется деревьев с корнями одинакового ранга, в полученном корневом списке необходимо найти элемент с минимальным ключом.

    Рассмотрим теперь, с помощью каких средств реализуется связывающий шаг. Для хранения ссылок на корни деревьев используем временный массив $${\rm RankT}$$, размера $$D(n)$$. Величина $${\rm RankT}[i]$$ будет указателем на тонкое дерево ранга $$i$$. Если найдется еще одно дерево ранга $$i$$, то свяжем два дерева ранга $$i$$ в одно дерево ранга $$i + 1$$, в $$i$$ -й ячейке массива $${\rm RankT}$$ установим нулевой указатель и продолжим связывающую процедуру с вновь полученным деревом ранга $$i + 1$$.

    При включении списка детей необходимо учесть возможность помеченности детей минимального узла. То есть уменьшить их ранг там, где это необходимо. Это требование вытекает из свойства 2 определения тонкого дерева. Очевидно, что для проверки помеченности узла требуется $$O(1)$$ операций.

    В результате выполнения связывающих шагов получаем заполненный массив $${\rm RankT}$$. Теперь остается только связать все деревья, находящиеся в этом массиве, в корневой список и найти в этом списке новый минимальный элемент. Очевидно, все это можно выполнить с трудоемкостью $$O(D(n))$$.

    Чтобы оценить амортизационную стоимость операции $${\rm DeleteMin}$$, подсчитаем фактическую стоимость операции и изменение потенциала. Фактическая стоимость складывается из $$O(1)$$ операций на проверку кучи на пустоту, $$O(D(n))$$ действий при добавлении детей минимального узла в корневой список и $$O$$ (количество связывающих шагов) + $$O(D(n))$$ при выполнении связывающих шагов.

    В итоге фактическая стоимость операции удаления минимального элемента есть $$O$$ (количество связывающих шагов) + $$D(n)$$.

    Очевидно, что потенциал уменьшился, как минимум, на число связывающих шагов, так как при каждом связывающем шаге количество деревьев в корневом списке уменьшается на единицу. Поскольку амортизационная стоимость равна фактической стоимости плюс изменение потенциала, то амортизационная стоимость равна $$O(D(n))$$.

    Операция DecreaseKey $$(\Dl, i, H).$$ При уменьшении ключа у некорневого элемента $$i$$ в куче $$H$$ на величину $$\Dl$$ может быть нарушено свойство кучеобразности. Для восстановления этого свойства перемещаем поддерево с корнем в изменяемом элементе в корневой список, но при этом, возможно, оставшееся после переноса дерево может не оказаться тонким.

    Покажем, как, затратив $$O(1)$$ амортизированного времени, исправлять его структуру. В процедуре $${\rm DecreaseKey}$$ после уменьшения ключа корректируется, если это необходимо, указатель на минимальный элемент кучи. После этого проверяется, не является ли измененный узел $$x$$ корнем дерева $$T$$. Если это действительно так, то процедура завершается, в противном случае переносим поддерево с корнем в узле $$x$$ в корневой список кучи и запускаем процедуру коррекции оставшегося дерева $$T'$$.

    Будем различать два вида нарушений свойств тонкого дерева:

  • Братские нарушения — это нарушения третьего правила из определения тонкого дерева.
  • Родительские нарушения — это нарушения первого или второго правила.
    •

    Рассмотрим подробнее каждое из двух видов нарушений. Назовем узел $$y$$ узлом локализации братского нарушения среди детей узла $$z$$, если ранг узла $$y$$ отличается от ранга его ближайшего правого брата на 2, либо он не имеет правого брата и его ранг равен 1. Пример — на рис. 8.3.

    (рис 8.3)

    Назовем узел $$y$$ узлом локализации родительского нарушения, если выполнено одно из трех условий:

  • Ранг узла $$y$$ на три больше, чем ранг его самого левого сына.
  • Ранг узла $$y$$ равен двум, и он не имеет детей.
  • Узел $$y$$ есть помеченный корень дерева.
    •

    Пример приведен на рис. 8.4.

    (рис 8.4)

    Рассмотрим теперь, как можно перестроить дерево, чтобы избавиться от братского нарушения либо свести его к родительскому. Пусть узел $$y$$ — это узел локализации братского нарушения. Рассмотрим два возможных варианта.

    Узел $$y$$ не помечен, то есть ранг его самого левого сына на единицу меньше ранга самого узла $$y$$. Пример — на рис. 8.5.

    (рис 8.5)

    В данном случае, чтобы исправить братское нарушение, помещаем на место пропущенного в братском списке поддерева поддерево с корнем в самом левом сыне узла $$y$$. Узел $$y$$ при такой операции становится помеченным, но зато дерево теперь удовлетворяет всем трем свойствам определения тонкого дерева. Очевидно, что это операция заканчивает процедуру исправления дерева.

    Узел $$y$$ помечен, тогда уменьшаем ранг узла $$y$$ на единицу. Это не исправит дерева, но зато теперь узлом локализации нарушения будет левый брат узла $$y$$ либо его родитель. В последней ситуации нарушение становится родительским. Пример приведен на рис. 8.6.

    (рис 8.6)

    Таким образом, мы либо исправим структуру дерева, либо рекурсивно придем к узлу локализации родительского нарушения.

    Выясним, чтo же делать с родительскими нарушениями. Пусть узел $$y$$ — это узел локализации родительского нарушения, а узел $$z$$ — родитель узла $$y$$. Тогда предлагается переместить поддерево с корнем в узле $$y$$ в корневой список кучи, делая при этом узел $$y$$ непомеченным. Считаем, что $$z$$ — это не корень дерева. Если узел $$z$$ не был помечен, то, очевидно, процедура исправления дерева закончена. Если он был помечен, то считаем его узлом локализации нового родительского нарушения. При этом, очевидно, количество помеченных узлов уменьшится на единицу. Продолжая такого вида рекурсивные шаги, мы либо дойдем до корня дерева, либо исправим его структуру раньше. Если узел $$z$$ стал корнем, то для того чтобы исправить структуру дерева, необходимо лишь сделать ранг корня на единицу большим ранга его самого левого сына. На этом процедура исправления дерева будет закончена.

    Заметим, что каждый промежуточный шаг рекурсии уменьшает число помеченных узлов на единицу и добавляет в корневой список не более одного дерева. Тогда потенциал при каждом шаге рекурсии уменьшается как минимум на единицу. Отсюда и следует обещанная оценка $$O(1)$$ времени выполнения операции $${\rm DecreaseKey}$$.

    Операция Delete(i,H) удаляет элемент $$i$$ из кучи $$H$$ следующим образом. Ключ удаляемого элемента $$i$$ уменьшается до некоторого значения, меньше минимального, и элемент удаляется как минимальный. Очевидно, что трудоемкость этой операции есть $$O(D(n))$$.

    Итак, амортизационная трудоемкость выполнения операций\linebreak $${\rm DeleteMin}$$ и $${\rm Delete}$$ на тонкой куче из $$n$$ элементов равна $$O(\log n)$$, а для остальных операций, как было показано ранее, — $$O(1)$$.

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^