Абстрактные типы данных. Структуры данных

Приоритетная очередь
(priority queue)
Абстрактные типы данных

Приоритетная очередь (англ. priority queue)
Предположим, что для каждого элемента определён некоторый приоритет. В простейшем случае значение приоритета может совпадать со значением элемента. В общем случае соотношение элемента и приоритета может быть произвольным.
Приоритетной очередью называется такой абстрактный тип данных, интерфейс которого включает в себя следующие операции:
PullHighestPriorityElement() — поиск и удаление элемента с самым высоким приоритетом;
InsertWithPriority(x, prior(x)) — добавление элемента x с указанным приоритетом

Хотя приоритетные очереди часто ассоциируются с кучами, они концептуально отличаются от куч.
Приоритетная очередь — это абстрактное понятие.
По аналогии с тем, как список (list) может быть реализован с помощью связного списка (linked list) или массива (array), приоритетная очередь (priority queue) может быть реализована с помощью кучи (heap) или другими способами (stack, queue, deque …)

Бинарная куча (binary heap)
Биномиальная куча (binomial heap)
Куча Фибоначчи (Fibonacci heap )
Структуры данных

Куча (англ. heap) — специализированная древовидная структура данных, которая удовлетворяет свойству кучи.
В вершинах древовидной структуры хранятся ключи.
Различают два варианта куч: min-heap и max-heap.
если вершина с ключом y является потомком вершины с ключом x, то x ≤ y.
если вершина с ключом y является потомком вершины с ключом x, то x ≥ y.
Cвойство кучи для max-heap
В дальнейшем, если не оговорено иное, будем считать, что при работе с кучей у нас вариант min-heap.

Существует много способов реализации структуры данных «куча» с помощью корневых деревьев:
1. Бинарная куча (англ. binary heap), или пирамида – реализация кучи с помощью полного бинарного дерева.
2. Биномиальная куча – реализация кучи с помощью семейства биномиальных деревьев
3. Куча Фибоначчи – реализация с помощью семейства корневых деревьев

GetMin() — поиск минимального ключа;
IncreaseKey
DecreaseKey
— модификация ключа вершины на заданную величину
(предполагается, что известна позиция вершины внутри структуры данных);
Базовый набор операций:
Расширенный набор операций:
ExtractMin() — удаление минимального ключа;
Insert(x) — добавление ключа x.
Heapify — построение кучи для последовательности из n ключей.

Бинарная куча (англ. binary heap)
Полное бинарное дерево —
это такое корневое дерево, в котором каждая вершина имеет не более двух сыновей, а заполнение вершин осуществляется в порядке от верхних уровней к нижним, причём на одном уровне заполнение вершинами производится слева направо. Пока уровень полностью не заполнен, к следующему уровню не переходят.
Последний уровень в полном бинарном дереве может быть заполнен не полностью.
Бинарная куча, или пирамида – реализация кучи с помощью полного бинарного дерева.
верхний уровень
нижний уровень

20
21
20
21
Максимальное число вершин в полном бинарном дереве высоты h
Минимальное число вершин в полном бинарном дереве высоты h

Высота h полного бинарного дерева, содержащего n вершин, — O(log n).

В памяти компьютера полное бинарное дерево легко реализуется с помощью массива.
Если предположить, что индексы массива начинаются с единицы, то для элемента с индекcом i сыновьями являются элементы с индексами 2i и 2i + 1, а родителем является элемент массива по индексу ⌊i/2⌋.
В памяти компьютера бинарная куча будет храниться в массиве следующим образом:
n=11
(число элементов в куче)
Пример.

В памяти компьютера указанное бинарная куча будет храниться в массиве следующим образом:
Если предположить, что индексы массива начинаются с нуля, то для перехода от 1-индексации к 0-индексации:
вместо i подставим i′=i+1,
затем из результата вычтем 1.
Cыновьями элемента i являются элементы с индексами
2(i+1)−1 = 2i+1,
[2(i+1)+1]−1 = 2i+2.
Родителем элемента i является элемент
⌊(i + 1)/2⌋ − 1 = ⌊(i − 1)/2⌋.
Пример.

GetMin() — поиск минимального ключа
1
3
2
3
5
4
1
9
9
7
8
def GetMin(a):
return a[0]

ExtractMin() — удаление минимального ключа
1
3
2
3
5
4
1
9
9
7
8
n=11
a
i
n=10
1
3
2
3
5
4
9
9
7
8
n=10
1
9
2
9

def ExtractMin(a):
a[0] = a[len(a) - 1]
a.pop()
i = 0
while 2 * i + 1 < len(a):
if (2 * i + 2 == len(a)) or (a[2 * i + 1] < a[2 * i + 2]):
j = 2 * i + 1 # left child
else:
j = 2 * i + 2 # right child
if a[i] <= a[j]:
break
a[i], a[j] = a[j], a[i] # swap
i = j

ExtractMin() — удаление минимального ключа

Insert(x) — добавление ключа x
1
3
2
3
5
4
1
9
9
7
8
n=11
a
i
n=12
n=12
1
3
2
3
5
4
1
9
7
8
0
1
3
5
6
9
8
7
2
4
9
10
0
11
3
0
1
0
1
0

def Insert(a, x):
a.append(x)
i = len(a) - 1
while i > 0:
j = (i - 1) // 2 # a[j] is the parent of a[i]
if a[j] <= a[i]:
break
a[i], a[j] = a[j], a[i] # swap
i = j

Insert(x) — добавление ключа x

DecreaseKey
уменьшение ключа вершины на заданную величину
(предполагается, что известна позиция вершины внутри структуры данных);
1
3
2
3
5
4
1
9
9
7
8
1
3
2
3
0
4
1
9
9
7
8
до модификации
в момент модификации
(элемент по индексу 4 уменьшили на число 5)
после модификации
1
3
3
0
4
1
9
9
7
8
2
3
0
1
0

IncreaseKey
увеличение ключа вершины на заданную величину
(предполагается, что известна позиция вершины внутри структуры данных);
1
3
2
3
5
4
1
5
9
7
8
до модификации
1
2
3
1
5
9
7
8
после модификации
5
4
9
4
9
5
9

DecreaseKey
уменьшение ключа вершины на заданную величину
IncreaseKey
увеличение ключа вершины на заданную величину
предполагается, что известна позиция вершины внутри структуры данных

Heapify построение кучи для последовательности из n ключей.
n=11
1. Строим полное бинарное дерево
1
3
6
0
8
7
2
9
0
1
2. Просеивание
2
Пример.
Построить бинарную кучу для последовательности элементов: 7,3,1,8,2,0,6,1,2,0,9
2
0
8
1
1
0
3
0
2
3
7
0
7
1
?
n=11

Для того, чтобы оценить время работы построения бинарной кучи для последовательности из n элементов, необходимо оценить суммарное число всех просеиваний. Число просеиваний равно сумме высот всех вершин дерева.

Так как число вершин полного бинарного дерева высоты h удовлетворяет неравенствам:
Получаем оценку сверху на число просеиваний:
Время работы алгоритма построения бинарной кучи:

Heapify построение кучи для последовательности из n ключей:

GetMin()
поиск минимального ключа;
IncreaseKey
DecreaseKey
модификация ключа вершины на заданную величину
(предполагается, что известна позиция вершины внутри структуры данных);
Базовый набор операций:
Расширенный набор операций:
ExtractMin() —
удаление минимального ключа;
Insert(x) —
добавление ключа x.
Heapify —
построение кучи для последовательности из n ключей.
Время выполнения базовых операций для бинарной кучи, содержащей n вершин:

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

Биномиальная куча
B0
B1
B2
B3
Семейство биномиальных деревьев:
у биномиального дерева высоты h на глубине d находится ровно Сdh вершин
Биномиальная куча – это биномиальный лес, для которого выполняются следующие свойства:
Инвариант 1: каждая вершина удовлетворяет основному свойству кучи: приоритет отца не ниже приоритета каждого из его сыновей;
Инвариант 2: в семействе биномиальных деревьев нет двух деревьев с корнями одинакового ранга (ранг вершины – количество её сыновей, ранг дерева – ранг корня).
в биномиальном дереве у вершины высоты h сыновья – биномиальные деревья B0 ,B1 ,…., Bh-1

Свойства семейства биномиальных деревьев:
по построению биномиальное деревоBh содержит 2h вершин;
для биномиального дерева ранг любой вершины совпадает с её высотой;
если в дереве Bh содержится n вершин, то его высота h=log n;
Любая последовательность из n элементов может быть представлена единственным образом как семейство биномиальных деревьев, в котором не более одного дерева каждого ранга.
Разложим число n по степеням 2. Например, если n=13=23+22+20, то семейство биномиальных деревьев состоит из деревьев B3, B2 , B0
Пусть в семействе из k уникальных биномиальных деревьев n вершин (обозначим через nmin минимально возможное число вершин в таком семействе):
так как ранг дерева равен его высоте, то для дерева Bh его ранг равен log n, где n – число вершин дерева;
B0
B1
B2
B3

Дополнительные вспомогательные операции link и cut,
которые нужны для выполнения базовых операций
x
y
x
y
+
link(x,y)
cut(y)
x
y
z
u
x
z
u
y
x≤y

1
0
4
3
5
4
9
7
8
2
7
Insert(x) — добавление ключа x.
3
0
4
3
5
4
9
7
8
2
7
3
Инвариант 1 всегда будет выполняться.
Для восстановления инварианта 2
выполним серию операций link над деревьями одного ранга:
B0
Так как каждый link уменьшает число деревьев на 1, а число деревьев в биномиальном семействе из n вершин есть O(log n), то время работы операции добавления ключа:
1

1
0
4
3
5
4
9
7
8
2
7
GetMin() — поиск минимального ключа;
хранят указатель на корень дерева с минимальным ключом и поддерживают его в процессе выполнения других операций;

1
0
4
3
5
4
9
7
8
2
7
ExtractMin() — удаление минимального ключа;
4
3
5
4
9
7
8
2
7
1
4
3
5
4
9
7
8
2
7
1) после серии
cut:
2) выполним серию операций link над деревьями одинакового ранга для восстановления инварианта 2:
Так как каждый link уменьшает число деревьев на 1, а число деревьев в семействе есть O(log n), то время работы операции удаления минимального элемента:
1

Heapify — построение кучи для последовательности из n ключей
Биномиальную кучу будем строить вызовом n раз функции Insert(x).
1-й элемент:
2-й элемент:
3-й элемент:
n-й элемент:
Оценим число биномиальных деревьев
после выполнения каждой операции Insert (x)
0+1- t1
(1- t1)+1-t2=2-(t1+t2)
2-(t1+t2) +1-t3=3-(t1+t2+t3)
n-(t1+t2+t3+…+ tn)
…
Обозначение
ti - число операций link, которые были выполнены при добавлении элемента x.

то время работы алгоритма Heapify построения кучи для последовательности из n ключей в худшем случае есть
Усреднённая оценка операции добавления элемента в биномиальную кучу:
предположим, что в биномиальной куче было изначально z0 деревьев;
выполним k раз операцию Insert(x);
просуммируем затраченное в худшем случае время;
разделим полученное значение на число выполненных операций.
Так как

Предполагается, что задана позиция вершины внутри структуры данных.
0
4
3
5
2
9
7
8
DecreaseKey (уменьшение ключа)
Уменьшаем ключ вершины x и просеиваем (обменами с отцом) элемент x до тех пор, пока для него не выполнится свойство кучи.
Так как один обмен выполняется за O(1), а количество обменов ограничено высотой дерева h=O(logn), то описанный алгоритм выполнит операцию уменьшения ключа за время:
1
1
2
1
7

IncreaseKey(увеличение ключа)
Увеличиваем ключ вершины x.
Если после этого для x нарушается свойство кучи, то просеиваем её (обменами с наименьшим из сыновей) тех пор, пока не выполнится инвариант 1.
Так как одно просеивание выполняется за O(log n), а число просеиваний ограничено высотой дерева h= O(log n), то алгоритм 1 выполнит операцию увеличения ключа за время:
0
4
3
5
2
9
7
8
Алгоритм 1
8
8
8
2
7
x

Увеличиваем ключ вершине x.
Время работы алгоритма:
Если инвариант 1 для x НЕ выполняется, то
3.1. Применяем операцию cut к самой вершине x и ко всем её сыновьям.
Пусть f – отец вершины x.
3.2. Восстанавливаем инвариант 2:серия операций link над «отрезанными» деревьями одного ранга (каждое из этих деревьев – биномиальное).
Суммарное число link - O(log n).
3.3. Полученное дерево «прикрепляем» к f.
Алгоритм 2
IncreaseKey(увеличение ключа)
2. Если инвариант 1 для x выполняется, то процедура увеличения ключа завершена.

0
4
3
5
2
9
7
8
1
6
7
8
2
4
5
6
3
4
3
5
2
9
7
8
6
7
8
4
5
6
Алгоритм 2
f
x
f
3
2
0

GetMin() — поиск минимального ключа;
IncreaseKey
DecreaseKey
— модификация ключа вершины на заданную величину
(предполагается, что известна позиция вершины внутри структуры данных);
Базовый набор операций:
Расширенный набор операций:
ExtractMin() — удаление минимального ключа;
Insert(x) — добавление ключа x.
Heapify — построение кучи для последовательности из n ключей.
Время выполнения базовых операций для биномиальной кучи, содержащей n вершин:

Куча Фибоначчи
(Fibonacci heap)
была предложена Майклом Фридманом
и
Робертом Тарьяном
в 1984 году.

Куча Фибоначчи – это семейство корневых деревьев, для которого выполняются следующие свойства (инварианты):
Инвариант 1. Каждая вершина в куче Фибоначчи удовлетворяет основному свойству кучи: приоритет отца не ниже приоритета каждого из его сыновей.
Инвариант 2. В семействе корневых деревьев нет двух деревьев с корнями одинакового ранга.
Инвариант 3. Каждая некорневая вершина в куче Фибоначчи может потерять не более одного сына при выполнении процедуры cut.
Название «кучи Фибоначчи» обусловлено тем, что для доказательства оценок трудоемкости операций используются числа Фибоначчи.
ранг любого узла в куче Фибоначчи
не превосходит:
если в куче n вершин, то число деревьев в ней:
В.М. Котов, Е. П. Соболевская, А. А. Толстиков. «Алгоритмы и структуры данных»: учеб. пособие Минск: БГУ, 2011г. C. 97 – 109.

DecreaseKey (уменьшение ключа)
-1
3
5
2
9
7
8
1
7
8
2
5
6
0
операции cut, которые выполняются для восстановления инварианта 1 будем называть исходными cut (cut)
операции cut, которые выполняются для восстановления инварианта 3 будем называть порождёнными cut (cut')
(на рисунке синяя заливка у некорневых вершин, которые ранее уже теряли сына)
cut(0)
cut'(2)
cut'(1)
Восстановление инварианта 3:
серия порожденных cut'
Восстановление инварианта 2:
серия операций link над деревьями одного ранга
Восстановление инварианта 1:
одна исходная операция cut
Выполнены:
3
5
2
9
7
8
1
7
8
2
6
0
-1

3
5
2
9
7
8
1
7
8
2
9
9
cut(7)
cut'(2)
cut'(1)
Восстановление инварианта 3:
серия порожденных cut'
Восстановление инварианта 2:
серия операций link над корневыми деревьями одного ранга
Восстановление инварианта 1:
исходные операция cut - O(log n)
Выполнены:
3
5
2
9
7
8
1
8
7
2
7
-1
7
8
cut(8)
cut'(9)
9
9
8
(на рисунке синяя заливка у некорневых вершин, которые уже потеряли 1 сына)
В худшем случае не можем оценить время работы алгоритма модификации ключа, так как не известна высота дерева.
Будем оценивать усреднённое время работы операции.
IncreaseKey
(увеличение ключа)
-1

Предположим, что мы выполнили некоторое число исходных операций cut, а они привели к выполнению серии порождённых операций cut' и link.
Справедливы следующие утверждения:
2. Число процедур link равно, как максимум, m плюс число всех процедур cut, где m – начальное число корневых деревьев:
n(link) ≤ m + n(cut') + n(cut )
Общее число порожденных операций cut' не превышает общего числа исходных cut :
n(cut') ≤ n(cut )
В.М. Котов, Е. П. Соболевская, А. А. Толстиков. «Алгоритмы и структуры данных»: учеб. пособие Минск: БГУ, 2011г. C. 97 – 109.

Усреднённая оценка трудоемкости операции добавления нового элемента:
Усреднённая оценка трудоемкости операции уменьшения ключа (задана ссылка на элемент в структуре):
Усреднённая оценка трудоемкости операции увеличения ключа (задана ссылка на элемент в структуре):
Усреднённая оценка трудоемкости операции удаления минимального элемента:
Куча Фибоначчи

Применение на практике

ExtractMin() — удаление минимального ключа;
Heapify —
строим бинарную кучу для последовательности из n ключей.
2. Пока куча не станет пустой:
Пирамидальная сортировка («сортировка кучей», англ. heapsort)
Время работы сортировки кучей в худшем случае:

C++ std::sort()
Основой служит алгоритм быстрой сортировки – модифицированный QuickSort, он же IntroSort, разработанный специально для stl. Отличие от QuickSort состоит в том, что количество рекурсивных операций не идет до самого конца, как в чистом QuickSort. Если количество итераций (процедур разделения массива) превысило 1.5*log2(n), где n - длина всего массива, то рекурсивные операции прекращаются:
если количество оставшихся элементов меньше 32-х, то оставшийся фрагмент сортируется методом вставки InsertionSort;
если количество оставшихся элементов более 32-х элементов, то этот фрагмент сортируется пирамидальным методом HeapSort в чистом его виде.

Сжатие информации.
Алгоритм префиксного кодирования Хаффмана

Метод разработан в 1952 году
аспирантом Массачусетского технологического института
Дэвидом Хаффманом при написании им курсовой работы

На вход поступает текст. По тексту строится таблица частот встречаемости символов.
Строится дерево кодирования Хаффмана (Н-дерево).
По H-дереву символам текста ставится в соответствие код - последовательность бит:
код - переменной длины, т.е. символам, которые встречаются чаще, соответствует битовый код меньшей длины;
код - префиксный, т.е. ни один из полученных кодов не является префиксом другого, что позволяет однозначно выполнять декодирование).

Каждому символу ставим в соответствие узел дерева, вес узла – частота встречаемости символа в тексте.
Полагаем все узлы - свободными.
Пока не останется 1 свободный узел, выполняем следующие действия:
находим 2 свободных узла v и w с минимальным весом и исключаем их из множества свободных узлов;
формируем новый свободный узел r, полагая v и w сыновьями r;
вес узла r определяем как сумму весов v и w.
4) Обходим дерево, ставя метки дугам дерева «0» или «1» (например, «0» – левому сыну, а «1» – правому).
Н-дерево

2
ё -1
г -1
и -3
6
к -4
3
ж -1
б -10
15
9
е -5
a -12
22
37
0
0
0
0
0
0
0
1
1
1
1
1
1
1
Н-дерево

2
ё
1
г
1
и
3
6
к
4
3
ж 1
б
10
15
9
е
5
a
12
22
37
0
0
0
0
0
0
0
1
1
1
1
1
1
1
Битовый код символа –
строка бит на пути от корня к этому символу.

Текст :
кажжекaa …
Закодированный текст:
Кодирование:
(010)(11 )( 0001)(0001)(011)(010)(11)(11)
к а ж ж е к a a

2
ё -1
г -1
и -3
6
к -4
3
ж -1
б -10
15
9
е -5
a -12
22
37
0
0
0
0
0
0
0
1
1
1
1
1
1
1
Декодирование:
для декодирования требуется H-дерево;
становимся на начало текста и в корень H-дерева;
двигаемся параллельно по тексту и дереву, пока не дойдём до листа дерева;
выписываем символ, который соответствует листу;
продолжаем далее движение по тексту, а в дереве становимся снова в корень;
1011100101100001000101011
Что закодировано в сообщении?

ЗАДАЧА
На вход поступает таблица частот встречаемости символов текста, который будет закодирован классическим алгоритмом Хаффмана. Вам дали эту таблицу, упорядочив символы в соответствии с их частотой встречаемости (сначала идут символы, которые реже всего встречаются в тексте).
Необходимо разработать эффективный! алгоритм, который определяет длину в битах текста после сжатия его методом Хаффмана (само сжатие выполнять не нужно) и оценить его время работы, указав используемые структуры данных.

2
ё -1
г -1
и -3
6
к -4
3
ж -1
б -10
15
9
е -5
a -12
22
37
0
0
0
0
0
0
0
1
1
1
1
1
1
1
по таблице частот строим H-дерево;
находим для каждого листа (=символа) его глубину (битовую длина символа);
перемножаем для каждого символа битовую длину на частоту встречаемости этого символа в тексте (это битовая длина всех вхождений символа в текст);
суммируем значения, полученные в (3), по всем символам текста;
(12*2) + (10*2) + (1*5) + (5*3) + (1*5) + (1*4) + (4*3) + (3*3) = 94 бита
если не сжимать текст, то получили: 37 * 8 бит = 296 бит
Наивный алгоритм
ответ

Какое время работы у Вашего «наивного алгоритма»?
Разработайте более эффективный алгоритм и проверьте себя, решив эту задачу в iRunner:
Кодирование Хаффмана

???
ЗАДАНИЕ
Выполнить общие задачи в iRunner
Тема 3. Структуры данных
0.3. Бинарная куча (проверка на соответствие структуре)
0.4. Биномиальная куча (понимание структуры)
ФПМИ БГУ
43. Кодирование Хаффмана