Здравствуйте, Хабросообщество!
На хабре есть описание множества интересных структур данных, таких как деревья отрезков, дуча и т.п. Если Вам интересны сложные структуры данных, то добро пожаловать под кат! В своем цикле статей я рассмотрю разные виды куч и способы их применения на практике:
1) Биномиальную кучу
2) Левую кучу
3) Фибоначчиеву кучу
4) Применение этих структур данных на практике
Постановка задачи:
Построить структуру данных, в которой будет храниться множество наших объектов (разных в зависимости от задачи), у каждого объекта будет поле ключ, по которому мы быстро сможем находить минимальный элемент. Для этой структуры должны бать возможны операции:
Многие знакомы с простейшими способами реализации этой структуры, такими как массив :) и двоичная куча. На них я не буду подробно останавливаться ввиду их простоты и общеизвестности.
Как известно, для двоичной кучи асимптотика перечисленных выше операций такова:
Описывать алгоритм работы двоичной кучи я не буду, так как он неоднократно описывался везде, в том числе и на Хабре. Для тех, кто не знаком с двоичной кучей, я бы порекомендовал прежде, чем продолжать чтение ознакомиться с ней.
Далее рассмотрим более интересную структуру данных, которая называется биномиальная куча.
Биномиальная куча
Биномиальная куча – это множество биномиальных деревьев с некоторыми ограничениями. Мы их введем чуть позже.
Биномиальное дерево – дерево, которое задается рекуррентно:
Bi – это Bi – 1, в котором левым сыном корня сделали дерево Bi – 1.
B0 — это просто вершина.
Примеры для B0, B2, B3:
У биномиального дерева(Bk) есть ряд интересных свойств:
T.1. 2k вершин
T.2. Высота дерева k
T.3. Ci k вершин глубины i (вот почему они называются биномиальными: Ci k биномиальный коэффициент).
T.4. Дети корня – это B, Bk – 2, …, B0 – именно в этом порядке.
T.5. Максимальная высота вершины в биномиальном дереве O(log N)
Доказываются свойства по индукции. Предлагаю читателям самим провести доказательство, для лучшего понимания деревьев.
Итак, теперь вернемся к биномиальным кучам. Биномиальная куча – множество биномиальных деревьев, со следующими ограничениями:
1) В каждом из биномиальных деревьев сохраняется свойство кучи.
2) Нет двух деревьев одинакового размера
3) Деревья упорядочены по размеру.
Поговорим о том, как биномиальная куча будет храниться в программе. Мы будем использовать метод “левый сын – правый брат”. Будем хранить корневой список(
Сразу же заметим:
Свойство H.1:
Длина
Для доказательства достаточно заметить, что из-за T.1, наличие дерева Bk в двоичной записи числа.
Перейдем к описанию операций, которые можно проводить с биномиальными кучами:
Make
Задача: создать пустую кучу.
Алгоритм: создаем пустой список
Сложность: очевидно, время работы O(1).
Merge
Задача: объединить 2 кучи в 1.
Алгоритм: сначала объединим корневые списки куч в 1 корневой список, поддерживая упорядоченность по degree. Алгоритм аналогичен слиянию 2-х массивов в mergeSort:
Храним по указателю на начало списков и в результирующий список записываем минимальный из них, тот откуда только что записали сдвигаем на следующий. Далее проходимся от начала до конца нового полученного корневого списка и сливаем деревья одинакового размера в 1. Могут быть случаи:
1) Только 2 дерева одинакового размера. Тогда объединяем их.
2) 3 дерева одинакового размера. Объединяем 2 последних.
При объединении двух деревьев нужно лишь посмотреть в корне какого из них меньший ключ и сделать другое дерево левым сыном корня этого дерева.
Пример, того, что получается после объединения двух куч:
Сложность: Время работы O(
За один проход (O(log N )) мы получим объединенное биномиальное дерево. Получаем, что общая сложность O(log N).
Insert
Задача: вставить новый элемент в кучу.
Алгоритм: Создаем кучу из одного элемента и объединяем с нашей кучей.
Сложность: O(1) + O(log(N)) = O(log(N)).
Minimum
Задача: найти минимум в куче.
Алгоритм: очевидно, минимум находится в корневом списке, то есть, чтобы его найти нужно пройтись по корневому списку.
Сложность: O(
ExtractMin
Задача: удалить минимальный элемент.
Алгоритм: находим его при помощи
Сложность: так как каждая операция в извлечении минимума работает за O(log N): O(log N) + O(log N) + O(log N) = O(log N)
Decrease
Задача: уменьшить значение data в данной вершине.
Алгоритм: уменьшаем значение в вершине. Тогда свойство кучи будет возможно нарушено для нашей вершины и ее предка, тогда меняем их местами. Продолжаем процесс, пока наша вершина не “всплывет” на свое место. Алгоритм работает также, как аналогичный в двоичной куче.
Сложность: В худшем случае наша вершина будет всплывать до корня, то есть мы совершим O(log N ) действий (вершина на каждом шаге “всплывает” на уровень выше, а высота биномиального дерева по T.5 O(log N))
Delete
Задача: удалить произвольный элемент.
Алгоритм: сначала уменьшим при помощи
Сложность: O(log N) + O(log N) = O(log N)
Заключение.
Мы рассмотрели структуру данных биномиальная куча и доказали ее асимптотику.
В следующей статье на основе биномиальной кучи мы построим чуть более сложную структуру данных, а именно Фибоначчиеву кучу.
Поиграться с биномиальными кучами можно на rain.ifmo.ru/cat/view.php/vis/heaps/binomial-2001
Почитать более подробно можно в Т.Кормен «Алгоритмы: построение и анализ.».
Всем спасибо за внимание, и до новых встреч!
На хабре есть описание множества интересных структур данных, таких как деревья отрезков, дуча и т.п. Если Вам интересны сложные структуры данных, то добро пожаловать под кат! В своем цикле статей я рассмотрю разные виды куч и способы их применения на практике:
1) Биномиальную кучу
2) Левую кучу
3) Фибоначчиеву кучу
4) Применение этих структур данных на практике
Постановка задачи:
Построить структуру данных, в которой будет храниться множество наших объектов (разных в зависимости от задачи), у каждого объекта будет поле ключ, по которому мы быстро сможем находить минимальный элемент. Для этой структуры должны бать возможны операции:
Make – создание новой пустой кучи,Insert – вставка нового элемента в кучу,Minimum – минимальный ключ,ExtractMin – извлечение минимума,Merge – слияние 2-х куч,Decrease – уменьшение ключа,Delete – удаление объекта.Многие знакомы с простейшими способами реализации этой структуры, такими как массив :) и двоичная куча. На них я не буду подробно останавливаться ввиду их простоты и общеизвестности.
Как известно, для двоичной кучи асимптотика перечисленных выше операций такова:
Make – O(1)Merge – O(N)Insert – O(log N) – где N – количество элементов в куче.Minimum – O(1)ExtractMin – O(log N)Decrease – O(log N)Delete – O(log N)Описывать алгоритм работы двоичной кучи я не буду, так как он неоднократно описывался везде, в том числе и на Хабре. Для тех, кто не знаком с двоичной кучей, я бы порекомендовал прежде, чем продолжать чтение ознакомиться с ней.
Далее рассмотрим более интересную структуру данных, которая называется биномиальная куча.
Биномиальная куча
Биномиальная куча – это множество биномиальных деревьев с некоторыми ограничениями. Мы их введем чуть позже.
Биномиальное дерево – дерево, которое задается рекуррентно:
Bi – это Bi – 1, в котором левым сыном корня сделали дерево Bi – 1.
B0 — это просто вершина.
Примеры для B0, B2, B3:
У биномиального дерева(Bk) есть ряд интересных свойств:
T.1. 2k вершин
T.2. Высота дерева k
T.3. Ci k вершин глубины i (вот почему они называются биномиальными: Ci k биномиальный коэффициент).
T.4. Дети корня – это B, Bk – 2, …, B0 – именно в этом порядке.
T.5. Максимальная высота вершины в биномиальном дереве O(log N)
Доказываются свойства по индукции. Предлагаю читателям самим провести доказательство, для лучшего понимания деревьев.
Итак, теперь вернемся к биномиальным кучам. Биномиальная куча – множество биномиальных деревьев, со следующими ограничениями:
1) В каждом из биномиальных деревьев сохраняется свойство кучи.
2) Нет двух деревьев одинакового размера
3) Деревья упорядочены по размеру.
Поговорим о том, как биномиальная куча будет храниться в программе. Мы будем использовать метод “левый сын – правый брат”. Будем хранить корневой список(
root_list, его длина root_list.length), в котором будут корни биномиальных деревьев, в порядке возрастания высоты. У каждой вершины будут следующие поля:data – данные, которые хранятся в вершине(по ним мы и находим минимум)right – правый братchild – левый сынdegree– степень вершины(очевидно деревья в биномиальной куче упорядоченны по этому полю)Сразу же заметим:
Свойство H.1:
Длина
root_list.length = O(log N), где N — количество элементов в куче.Для доказательства достаточно заметить, что из-за T.1, наличие дерева Bk в двоичной записи числа.
Перейдем к описанию операций, которые можно проводить с биномиальными кучами:
Make
Задача: создать пустую кучу.
Алгоритм: создаем пустой список
root_list.Сложность: очевидно, время работы O(1).
Merge
Задача: объединить 2 кучи в 1.
Алгоритм: сначала объединим корневые списки куч в 1 корневой список, поддерживая упорядоченность по degree. Алгоритм аналогичен слиянию 2-х массивов в mergeSort:
Храним по указателю на начало списков и в результирующий список записываем минимальный из них, тот откуда только что записали сдвигаем на следующий. Далее проходимся от начала до конца нового полученного корневого списка и сливаем деревья одинакового размера в 1. Могут быть случаи:
1) Только 2 дерева одинакового размера. Тогда объединяем их.
2) 3 дерева одинакового размера. Объединяем 2 последних.
При объединении двух деревьев нужно лишь посмотреть в корне какого из них меньший ключ и сделать другое дерево левым сыном корня этого дерева.
Пример, того, что получается после объединения двух куч:
Сложность: Время работы O(
root_list1.length) + O(root_list2.length) = (по свойству H.1) = O(log N).За один проход (O(log N )) мы получим объединенное биномиальное дерево. Получаем, что общая сложность O(log N).
Insert
Задача: вставить новый элемент в кучу.
Алгоритм: Создаем кучу из одного элемента и объединяем с нашей кучей.
Сложность: O(1) + O(log(N)) = O(log(N)).
Minimum
Задача: найти минимум в куче.
Алгоритм: очевидно, минимум находится в корневом списке, то есть, чтобы его найти нужно пройтись по корневому списку.
Сложность: O(
root_list.length) = O(log(N)).ExtractMin
Задача: удалить минимальный элемент.
Алгоритм: находим его при помощи
Minimum. Удаляем его из корневого списка. Из перевернутого списка его детей делаем root_list для новой кучи (H1) и объединяем исходную кучу с H1.Сложность: так как каждая операция в извлечении минимума работает за O(log N): O(log N) + O(log N) + O(log N) = O(log N)
Decrease
Задача: уменьшить значение data в данной вершине.
Алгоритм: уменьшаем значение в вершине. Тогда свойство кучи будет возможно нарушено для нашей вершины и ее предка, тогда меняем их местами. Продолжаем процесс, пока наша вершина не “всплывет” на свое место. Алгоритм работает также, как аналогичный в двоичной куче.
Сложность: В худшем случае наша вершина будет всплывать до корня, то есть мы совершим O(log N ) действий (вершина на каждом шаге “всплывает” на уровень выше, а высота биномиального дерева по T.5 O(log N))
Delete
Задача: удалить произвольный элемент.
Алгоритм: сначала уменьшим при помощи
Decrease значение в вершине до минимально возможного. А затем удалим минимальный в куче (ExtractMin).Сложность: O(log N) + O(log N) = O(log N)
Заключение.
Мы рассмотрели структуру данных биномиальная куча и доказали ее асимптотику.
В следующей статье на основе биномиальной кучи мы построим чуть более сложную структуру данных, а именно Фибоначчиеву кучу.
Поиграться с биномиальными кучами можно на rain.ifmo.ru/cat/view.php/vis/heaps/binomial-2001
Почитать более подробно можно в Т.Кормен «Алгоритмы: построение и анализ.».
Всем спасибо за внимание, и до новых встреч!