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

Ленивые левосторонние и самоорганизующиеся кучи

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

Ленивая левосторонняя куча

Ленивая левосторонняя куча — это представление приоритетной очереди левосторонним деревом, но при этом, в отличие от обычной левосторонней кучи, каждый узел может содержать, а может и не содержать в себе (быть пустым) элемент приоритетной очереди. Для реализации ленивой левосторонней кучи к каждому узлу добавляется еще одно поле, для хранения признака, содержит ли данный узел элемент или является пустым. Такие кучи носят название "ленивых" из-за способа выполнения операций УДАЛИТЬ и СЛИТЬ.

При выполнении операции УДАЛИТЬ узел не удаляется, а лишь помечается как пустой. Время "ленивого" выполнения этой операции равно $$O(1)$$.

Операция СЛИТЬ осуществляется следующим образом. Заводится пустой корневой узел, сыновьями которого становятся корневые узлы объединяемых куч. Время "ленивого" выполнения этой операций равно $$O(1)$$.

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

Утверждение. Время выполнения операции НАЙТИ_ЭЛЕМЕНТ_С МИНИМАЛЬНЫМ_КЛЮЧОМ является величиной$$\eq*{ O(k \max\{1, \log n /(k + 1)\}), }$$

где $$k$$ — количество верхних пустых элементов.

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

Операция ВСТАВИТЬ новый элемент $$x$$ в кучу $$h$$ производится посредством слияния кучи $$h$$ с кучей, содержащей единственный элемент $$x$$.

Операция ОБРАЗОВАТЬ_ОЧЕРЕДЬ в форме ленивой левосторонней кучи из элементов списка производится как в обычных левосторонних кучах, то есть с неленивыми слияниями.

Операция УМЕНЬШИТЬ_КЛЮЧ элемента $$x$$ на величину $$\Dl$$ выполняется следующим образом. Ключ элемента $$x$$ уменьшается на $$\Dl$$, узел, его содержащий, помечается как пустой, из этого элемента $$x$$ образуется новая одноэлементная куча, которая сливается с исходной кучей.

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

УДАЛИТЬ УЗЕЛ $$O(1)$$
НАЙТИ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ $$O(k \max\{1, \log n/(k + 1)\})$$
УДАЛИТЬ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ $$O(k \max\{1, \log n / (k + 1)\})$$
СЛИТЬ $$O(1)$$
ВСТАВИТЬ $$O(1)$$
ОБРАЗОВАТЬ ОЧЕРЕДЬ $$O(n)$$
УМЕНЬШИТЬ КЛЮЧ $$O(1)$$

Самоорганизующаяся куча

Самоорганизующаяся куча — это представление приоритетной очереди корневым деревом, операции с которым производятся аналогично операциям с левосторонней кучей, но без использования рангов. Длина правого пути из корня такого дерева в лист может быть произвольной, поэтому время выполнения всех операций в худшем случае есть $$O(n)$$, где $$n$$ — число элементов в очереди. Однако среднее время выполнения $$m$$ произвольных операций есть $$O(m \log n)$$, то есть время, приходящееся на одну операцию, как ни удивительно, является величиной $$O(\log n)$$. Для их реализации необходимо с каждым узлом дерева хранить элемент, его ключ, указатели на левое и правое поддеревья, то есть узлы представлять записями вида$$\eq*{ {\rm Node} = (\t element, \t key, \t left, \t right). }$$

Операция СЛИТЬ кучи $$h_1$$ и $$h_2$$ в одну кучу $$h$$ выполняется следующим образом. Правые пути двух исходных куч $$h_1$$ и $$h_2$$ сливаются в один путь, упорядоченный по правилам кучи, и этот путь становится левым путем результирующей кучи $$h$$. Левые поддеревья узлов, попавших в результирующий левый путь, становятся правыми.

Операция ВСТАВИТЬ в кучу $$h$$ новый элемент $$x$$ производится посредством слияния кучи $$h$$ с кучей, содержащей единственный элемент $$x$$. Таким образом, время выполнения этой операции равно времени выполнения операции СЛИТЬ.

Операция УДАЛИТЬ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ производится посредством удаления корня кучи $$h$$ и слияния его левой и правой подкуч. Таким образом, вычислительная сложность этой операции равна вычислительной сложности операции СЛИТЬ.

Операция НАЙТИ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ выполняется, очевидно, за время $$O(1)$$, так как этот элемент находится в корне.

Анализ времени выполнения операции СЛИТЬ. Поскольку время выполнения всех трудоемких операций определяется временем выполнения операции СЛИТЬ, остается проанализировать именно эту операцию. Очевидно, время ее выполнения пропорционально количеству узлов в правых путях исходных куч $$h_1$$ и $$h_2$$. Длина такого пути в худшем случае может зависеть линейно от количества узлов в соответствующей куче. Таким образом, время выполнения операции СЛИТЬ есть величина $$O(n_1+n_2) =O(n)$$, где $$n_1$$, $$n_2$$, $$n$$ — количества узлов в кучах $$h_1$$, $$h_2$$, $$h$$, соответственно.

Нахождение суммарной оценки времени выполнения m операций СЛИТЬ. Введем определение. Узел назовем тяжелым, если количество узлов в его правом поддереве строго больше, чем в левом. Остальные узлы назовем легкими.

Определим потенциал коллекции куч как общее количество содержащихся в ней тяжелых узлов. Пусть $$P_j$$ — потенциал коллекции после выполнения $$j$$ -й операции.

Утверждение. Время $$T$$ выполнения $$m$$ операций СЛИТЬ, примененных к коллекции, состоящей из $$(m + 1)$$ куч с нулевым потенциалом, является величиной $$O(m \log n)$$, где $$n$$ — общее количество узлов в коллекции.

Доказательство. Пусть $$i$$ -я операция заключается в слиянии куч $$h_1$$ и $$h_2$$ в результирующую кучу $$h$$. Пусть перед ее выполнением $$H_1$$ и $$H_2$$ — количества тяжелых узлов в правых путях куч $$h_1$$ и $$h_2$$ соответственно, $$L_1$$ и $$L_2$$ — количества легких узлов в этих путях, $$Q_1$$, $$Q_2$$ — количества тяжелых узлов в остальных частях куч.

Время выполнения этой операции с точностью до постоянного множителя оценивается сверху величиной $$C_i = (H_1 + L_1) + (H_2 + L_2)$$.

Подсчитаем изменение $$\Dl P_i$$ потенциала при ее выполнении. Имеем$$\eq*{ P_{i-1} = H_1 + Q_1 + H_2 + Q_2. }$$

По завершении этой операции тяжелые узлы правых путей становятся легкими, их количество равно $$H_1 + H_2$$. Легкие узлы правых путей могут как стать тяжелыми, так и остаться легкими, их будет не более $$L_1 + L_2$$ штук, а количества тяжелых узлов в остальной части обоих деревьев $$Q_1 + Q_2$$ не изменились. Следовательно, количество $$P_i$$ тяжелых узлов после выполнения операции удовлетворяет неравенству

$$\eq*{ P_i \le L_1 + Q_1 + L_2 + Q_2. }$$

Таким образом, получаем изменение потенциала

$$\Dl P_i = P_i - P_{i - 1} \le (L_1 + Q_1 + L_2 + Q_2) - (H_1 + Q_1 + H_2 + Q_2) = L_1 + L_2 - H_1 - H_2$$

и, следовательно,

$$\eq*{ C_i + \Dl P_i \le (H_1 + L_1 + H_2 + L_2) + (L_1 + L_2 - H_1 - H_2) = 2(L_1 + L_2). }$$

Из определения легкого узла следует, что количество $$L_i$$ легких узлов в куче $$h_i$$ $$(i = 1, 2)$$ не превосходит логарифма количества $$n_i$$ узлов в этой куче.

Следовательно,$$\eq*{ C_i+ \Dl P_i \le 2(L_1 + L_2) \le 2(\log n_1 + \log n_2) \le 2\log n_{12} \le 2\log n, }$$ где $$n_{12} = n_1 + n_2$$, а $$n$$ — общее количество узлов в исходных $$m$$ кучах.

Суммируя левую и правую части последнего неравенства по $$i = 1, 2\dts m$$, получаем, что величина $$T$$ с точностью до постоянного множителя оценивается сверху величиной, пропорциональной $$2m \log n$$, то есть принадлежит $$O(m \log n)$$.

Величина $$2\log n$$ является амортизационной оценкой времени выполнения операции СЛИТЬ, то есть величиной $$O(\log n)$$.

Замечание. Вначале коллекция, состоящая из $$m + 1$$ куч, к которым применяются $$m$$ операций СЛИТЬ, может иметь произвольное количество узлов, в сумме равное $$n$$. Важно, чтобы потенциал каждой из них, следовательно, и суммарный потенциал был равен нулю, то есть кучи не должны первоначально иметь тяжелых узлов.

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

Особое значение имеет случай, когда каждая из $$m + 1$$ начальных куч состоит из единственного узла.

Итак, для всех коллекций таких куч амортизационное время выполнения одной операции СЛИТЬ является величиной $$O(\log n)$$, где $$n$$ — общее количество их узлов.

Сводные данные о трудоемкости операций с самоорганизующимися кучами

Операция Верхняя оценка Амортизационная оценка
СЛИТЬ $$O(n)$$ $$O(\log n)$$
ВСТАВИТЬ $$O(n)$$ $$O(\log n)$$
УДАЛИТЬ_МИНИМУМ $$O(n)$$ $$O(\log n)$$
НАЙТИ_МИНИМУМ $$O(1)$$ $$O(1)$$
Страницы:

Ленивая левосторонняя куча

Ленивая левосторонняя куча — это представление приоритетной очереди левосторонним деревом, но при этом, в отличие от обычной левосторонней кучи, каждый узел может содержать, а может и не содержать в себе (быть пустым) элемент приоритетной очереди. Для реализации ленивой левосторонней кучи к каждому узлу добавляется еще одно поле, для хранения признака, содержит ли данный узел элемент или является пустым. Такие кучи носят название "ленивых" из-за способа выполнения операций УДАЛИТЬ и СЛИТЬ.

При выполнении операции УДАЛИТЬ узел не удаляется, а лишь помечается как пустой. Время "ленивого" выполнения этой операции равно $$O(1)$$.

Операция СЛИТЬ осуществляется следующим образом. Заводится пустой корневой узел, сыновьями которого становятся корневые узлы объединяемых куч. Время "ленивого" выполнения этой операций равно $$O(1)$$.

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

Утверждение. Время выполнения операции НАЙТИ_ЭЛЕМЕНТ_С МИНИМАЛЬНЫМ_КЛЮЧОМ является величиной$$\eq*{ O(k \max\{1, \log n /(k + 1)\}), }$$

где $$k$$ — количество верхних пустых элементов.

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

Операция ВСТАВИТЬ новый элемент $$x$$ в кучу $$h$$ производится посредством слияния кучи $$h$$ с кучей, содержащей единственный элемент $$x$$.

Операция ОБРАЗОВАТЬ_ОЧЕРЕДЬ в форме ленивой левосторонней кучи из элементов списка производится как в обычных левосторонних кучах, то есть с неленивыми слияниями.

Операция УМЕНЬШИТЬ_КЛЮЧ элемента $$x$$ на величину $$\Dl$$ выполняется следующим образом. Ключ элемента $$x$$ уменьшается на $$\Dl$$, узел, его содержащий, помечается как пустой, из этого элемента $$x$$ образуется новая одноэлементная куча, которая сливается с исходной кучей.

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

УДАЛИТЬ УЗЕЛ $$O(1)$$
НАЙТИ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ $$O(k \max\{1, \log n/(k + 1)\})$$
УДАЛИТЬ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ $$O(k \max\{1, \log n / (k + 1)\})$$
СЛИТЬ $$O(1)$$
ВСТАВИТЬ $$O(1)$$
ОБРАЗОВАТЬ ОЧЕРЕДЬ $$O(n)$$
УМЕНЬШИТЬ КЛЮЧ $$O(1)$$

Самоорганизующаяся куча

Самоорганизующаяся куча — это представление приоритетной очереди корневым деревом, операции с которым производятся аналогично операциям с левосторонней кучей, но без использования рангов. Длина правого пути из корня такого дерева в лист может быть произвольной, поэтому время выполнения всех операций в худшем случае есть $$O(n)$$, где $$n$$ — число элементов в очереди. Однако среднее время выполнения $$m$$ произвольных операций есть $$O(m \log n)$$, то есть время, приходящееся на одну операцию, как ни удивительно, является величиной $$O(\log n)$$. Для их реализации необходимо с каждым узлом дерева хранить элемент, его ключ, указатели на левое и правое поддеревья, то есть узлы представлять записями вида$$\eq*{ {\rm Node} = (\t element, \t key, \t left, \t right). }$$

Операция СЛИТЬ кучи $$h_1$$ и $$h_2$$ в одну кучу $$h$$ выполняется следующим образом. Правые пути двух исходных куч $$h_1$$ и $$h_2$$ сливаются в один путь, упорядоченный по правилам кучи, и этот путь становится левым путем результирующей кучи $$h$$. Левые поддеревья узлов, попавших в результирующий левый путь, становятся правыми.

Операция ВСТАВИТЬ в кучу $$h$$ новый элемент $$x$$ производится посредством слияния кучи $$h$$ с кучей, содержащей единственный элемент $$x$$. Таким образом, время выполнения этой операции равно времени выполнения операции СЛИТЬ.

Операция УДАЛИТЬ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ производится посредством удаления корня кучи $$h$$ и слияния его левой и правой подкуч. Таким образом, вычислительная сложность этой операции равна вычислительной сложности операции СЛИТЬ.

Операция НАЙТИ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ выполняется, очевидно, за время $$O(1)$$, так как этот элемент находится в корне.

Анализ времени выполнения операции СЛИТЬ. Поскольку время выполнения всех трудоемких операций определяется временем выполнения операции СЛИТЬ, остается проанализировать именно эту операцию. Очевидно, время ее выполнения пропорционально количеству узлов в правых путях исходных куч $$h_1$$ и $$h_2$$. Длина такого пути в худшем случае может зависеть линейно от количества узлов в соответствующей куче. Таким образом, время выполнения операции СЛИТЬ есть величина $$O(n_1+n_2) =O(n)$$, где $$n_1$$, $$n_2$$, $$n$$ — количества узлов в кучах $$h_1$$, $$h_2$$, $$h$$, соответственно.

Нахождение суммарной оценки времени выполнения m операций СЛИТЬ. Введем определение. Узел назовем тяжелым, если количество узлов в его правом поддереве строго больше, чем в левом. Остальные узлы назовем легкими.

Определим потенциал коллекции куч как общее количество содержащихся в ней тяжелых узлов. Пусть $$P_j$$ — потенциал коллекции после выполнения $$j$$ -й операции.

Утверждение. Время $$T$$ выполнения $$m$$ операций СЛИТЬ, примененных к коллекции, состоящей из $$(m + 1)$$ куч с нулевым потенциалом, является величиной $$O(m \log n)$$, где $$n$$ — общее количество узлов в коллекции.

Доказательство. Пусть $$i$$ -я операция заключается в слиянии куч $$h_1$$ и $$h_2$$ в результирующую кучу $$h$$. Пусть перед ее выполнением $$H_1$$ и $$H_2$$ — количества тяжелых узлов в правых путях куч $$h_1$$ и $$h_2$$ соответственно, $$L_1$$ и $$L_2$$ — количества легких узлов в этих путях, $$Q_1$$, $$Q_2$$ — количества тяжелых узлов в остальных частях куч.

Время выполнения этой операции с точностью до постоянного множителя оценивается сверху величиной $$C_i = (H_1 + L_1) + (H_2 + L_2)$$.

Подсчитаем изменение $$\Dl P_i$$ потенциала при ее выполнении. Имеем$$\eq*{ P_{i-1} = H_1 + Q_1 + H_2 + Q_2. }$$

По завершении этой операции тяжелые узлы правых путей становятся легкими, их количество равно $$H_1 + H_2$$. Легкие узлы правых путей могут как стать тяжелыми, так и остаться легкими, их будет не более $$L_1 + L_2$$ штук, а количества тяжелых узлов в остальной части обоих деревьев $$Q_1 + Q_2$$ не изменились. Следовательно, количество $$P_i$$ тяжелых узлов после выполнения операции удовлетворяет неравенству

$$\eq*{ P_i \le L_1 + Q_1 + L_2 + Q_2. }$$

Таким образом, получаем изменение потенциала

$$\Dl P_i = P_i - P_{i - 1} \le (L_1 + Q_1 + L_2 + Q_2) - (H_1 + Q_1 + H_2 + Q_2) = L_1 + L_2 - H_1 - H_2$$

и, следовательно,

$$\eq*{ C_i + \Dl P_i \le (H_1 + L_1 + H_2 + L_2) + (L_1 + L_2 - H_1 - H_2) = 2(L_1 + L_2). }$$

Из определения легкого узла следует, что количество $$L_i$$ легких узлов в куче $$h_i$$ $$(i = 1, 2)$$ не превосходит логарифма количества $$n_i$$ узлов в этой куче.

Следовательно,$$\eq*{ C_i+ \Dl P_i \le 2(L_1 + L_2) \le 2(\log n_1 + \log n_2) \le 2\log n_{12} \le 2\log n, }$$ где $$n_{12} = n_1 + n_2$$, а $$n$$ — общее количество узлов в исходных $$m$$ кучах.

Суммируя левую и правую части последнего неравенства по $$i = 1, 2\dts m$$, получаем, что величина $$T$$ с точностью до постоянного множителя оценивается сверху величиной, пропорциональной $$2m \log n$$, то есть принадлежит $$O(m \log n)$$.

Величина $$2\log n$$ является амортизационной оценкой времени выполнения операции СЛИТЬ, то есть величиной $$O(\log n)$$.

Замечание. Вначале коллекция, состоящая из $$m + 1$$ куч, к которым применяются $$m$$ операций СЛИТЬ, может иметь произвольное количество узлов, в сумме равное $$n$$. Важно, чтобы потенциал каждой из них, следовательно, и суммарный потенциал был равен нулю, то есть кучи не должны первоначально иметь тяжелых узлов.

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

Особое значение имеет случай, когда каждая из $$m + 1$$ начальных куч состоит из единственного узла.

Итак, для всех коллекций таких куч амортизационное время выполнения одной операции СЛИТЬ является величиной $$O(\log n)$$, где $$n$$ — общее количество их узлов.

Сводные данные о трудоемкости операций с самоорганизующимися кучами

Операция Верхняя оценка Амортизационная оценка
СЛИТЬ $$O(n)$$ $$O(\log n)$$
ВСТАВИТЬ $$O(n)$$ $$O(\log n)$$
УДАЛИТЬ_МИНИМУМ $$O(n)$$ $$O(\log n)$$
НАЙТИ_МИНИМУМ $$O(1)$$ $$O(1)$$
Предыдущее занятие Следующее занятие
Вернуться к учебному плану
^