close

Вход

Забыли?

вход по аккаунту

?

Алгоритмы и структуры данных. Лекция 5

код для вставкиСкачать
Деревья
Лекция 5
План лекции
1. Интерфейс абстракции множество
2. Интерфейс абстракции отображение.
3. Сбалансированные деревья поиска.
4. Красно-чёрные деревья.
5. Интерфейс абстракции приоритетная очередь
6. HeapSort
Интерфейс абстракции
множество.
Абстракция множество
I
Абстракция множество позволяет создавать объекты,
содержащие различные перечислимые элементы,
обращаясь к ним не по их номерам, а по их значению.
I
Пример: множество чисел {1, 5, 18}
I
Обращение по номерам для множества не применяется.
I
Трактовка множества максимально приближена к
использованию множеств в математике.
I
{1, 5, 18} ∪ {2} → {1, 2, 5, 18}
I
{1, 5, 18} ∪ {5} → {1, 5, 18}
I
{1, 5, 18} − {5} → {1, 18}
I
{1, 5, 18} ∩ {1, 7, 14, 18} → {1, 18}
Абстракция множество
I
Свойства множества:
I
I
I
I
каждый элемент может появиться ровно один раз
порядок элементов несущественен: {1, 5} ≡ {5, 1}
множество удобно записывать в упорядоченном виде
Полезность реализации множества определяется:
I
I
I
множеством допустимых значений элементов;
наличием необходимых операций;
эффективностью операций;
Абстракция множество
Интерфейс абстракции множество:
I
insert(key) — добавить элемент key
I
bool find(key) — определить наличие элемент со
значением key
I
erase(key) — удалить элемент со значением key
I
walk — получить все элементы в каком-либо порядке.
I
size — получить размер множества.
Возможно, для добавления или удаления элемента потребуется
поиск элемента.
Абстракция множество
Возможные представления множеств:
I Неотсортированный массив.
I
I
I
Отсортированный массив.
I
I
I
I
insert, find, remove — O(|S|)
Память: O(|S|) элементов
insert, remove — O(|S|)
find — O(log |S|)
Память: O(|S|) элементов
Отсортированный двусвязный список.
I
I
insert, remove, find — O(log |S|)
Память: O(|S|) элементов
Абстракция множество
I
Представление в виде битовой карты.
I
Создаётся битовый массив M размера |D(key )|.
I
Наличие бита говорит о наличии элемента в множестве.
S = {1, 5, 11}
Пусть D(key ) = {0, 1, . . . , 15}
Тогда M = {0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}
Машинное представление M равно 211 + 25 + 21 .
Операция S + {6} = {1, 5, 6, 11} →
M = M | 2^6
Операция S + {5} = {1, 5, 11} →
M = M | 2^5
Операция S − {5} = {1, 11} →
M = M & ~(2^5)
Абстракция множество
Возможные представления множеств:
I Битовая карта.
I
I
I
insert, find, remove — O(1)
Память: O(|D(key )|) элементов
size — O(1) или O(|D(key )|)
Абстракция множество
I
I
Пример неудачной реализации множества — язык Паскаль.
Тип «множество» присутствует, но:
I
I
I
I
множество не может содержать более 255 элементов
каждый из элементов должен принимать значения от 0 до
255
не имеется операций определения размера множества
не имеется операции перечисления элементов множества
(в некоторых диалектах есть)
Абстракция отображение
Цели:
I Реализовать операции, исполняющиеся минимальное
время:
I
I
I
I
I
Вставки
Замены
Удаления
Поиска
Перечисления
Интерфейс абстракции
отображение.
Абстракция отображение
I
Абстракция отображение устанавливает соответствие
между двумя множествами — множеством ключей и
множеством данных.
Шанхай
24150000
Карачи
23500000
Пекин
21150000
Дели
17830000
Лагос
17060000
Стамбул
14160000
Абстракция отображение
I
Абстракция отображение есть аналог дискретной функции.
I
Одно из определений математической функции: Функция
есть отображение множества D на множество E .
F(x)
D(x)
E(x)
Абстракция отображение
I
Самый удобный способ создать отображение —
воспользоваться синтаксисом индексации.
map m;
m["Шанхай"] = 24150000;
m["Карачи"] = 23500000;
m["Пекин"] = 21150000;
m["Дели"]
= 17830000;
...
int BeijingPopulation = m["Пекин"];
...
for (auto x: m) {
printf("Population of ’%s’ is %d\n",
x.first, x.second);
Абстракция отображение
Интерфейс абстракции отображение
I
insert(key, value) — добавить элемент с ключом key и
значением value
I
Item find(key) — найти элемент с ключом key и вернуть
его.
I
erase(key) — удалить элемент с ключом key
I
walk — получить все ключи (или все пары ключ/значение)
в каком-либо порядке.
Абстракция отображение
Цели:
I Реализовать операции, исполняющиеся минимальное
время:
I
I
I
I
I
Вставки
Замены
Удаления
Поиска
Перечисления
В дальнейшем под термином ключ мы понимаем пару
ключ+значение, в которой определена операция сравнения
по ключу.
Связь множества и отображения
I
Возможная реализация отображения — множество с
прикреплёнными данными.
I
Каждое представление множества, кроме битовой карты,
расширяется на отображение.
I
С другой стороны — множество есть отображение
множества ключей на логическую истину.
I
Наиболее универсальное представление и множеств, и
отображений — двоичное дерево поиска.
Ещё про двоичные деревья
поиска
Двоичные деревья поиска
Вспомним про проблемы с наивным построением двоичных
деревьев поиска.
Неплохое дерево
{10, 5, 35, 7, 3, 23, 94, 2, 5, 7}
10
5
35
3
2
7
5
7
23
94
Двоичные деревья поиска
Отвратительное дерево
{1, 5, 10, 20, 30}
1
5
10
20
30
Двоичные деревья поиска
Определение:
I
Полное двоичное дерево TH высоты H есть двоичное
дерево, у которого путь от корня до любой вершины
содержит ровно H рёбер, при этом у всех узлов дерева, не
являющимися листьями, есть и правый, и левый потомок.
Полное двоичное дерево высоты 3.
A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
Двоичные деревья поиска
Рекурсивное определение:
I
Полное двоичное дерево TH высоты H есть двоичное
дерево, у которого к корню прикреплены левое и правое
поддеревья TH−1 высоты H − 1.
I
По этому определению число узлов в дереве TH есть
N = 2H+1 − 1
H = log2 (N + 1)
Двоичные деревья поиска
Определение:
I
Случайное двоичное дерево T размера n — дерево,
получающееся из пустого двоичного дерева поиска после
добавления в него n узлов с различными ключами в
случайном порядке и все n! возможных
последовательностей добавления равновероятны.
Двоичные деревья поиска
Определение средней глубины случайного дерева.
¯ + 1) — средняя глубина всех узлов случайного
I Пусть d(N
дерева с N + 1 узлами.
I
I
Пусть k — узел, добавленный первым. Вероятность
1
добавления узла k есть pk =
N +1
Остальные узлы разобьются на группы, каждая из которых
начнётся с высоты 1. В левую группу войдут элементы
{0, . . . , k − 1}, в правую — {k + 1, . . . , N}.
¯ + 1) =
d(N
N
X
k=0
1
N +1
k ¯
N −k ¯
1 + · d(k) +
· d(N − k)
N
N
Двоичные деревья поиска
N
¯ + 1) =
d(N
X
2
¯
k · d(k)
N(N + 1)
k=0
Используя предел
lim
n→∞
n
X
1
− ln n
k
!
= γ = 0.57721...
k=1
получаем
¯
lim (d(N)
− 2 ln N) → C
N→∞
Двоичные деревья поиска
I
Средняя глубина узлов случайного двоичного дерева есть
Θ(log2 N).
I
Средние времена выполнения операций вставки, удаления
и поиска в случайном двоичном дереве есть Θ(log2 N).
Двоичные деревья поиска: свойства
Полезные свойства двоичного дерева поиска:
I
Наименьший элемент всегда находится в самом низу
левого поддерева.
I
Наибольший элемент всегда находится в самом низу
правого поддерева.
tree * minNode(tree *t) {
if (t == NULL) return NULL;
while (t->left != NULL) {
t = t->left;
}
return t;
}
Двоичные деревья поиска: свойства
I
Простая процедура поиска
tree * searchNode(tree *t, keytype key) {
tree *p = t;
while (t != NULL) {
p = t;
if (t->key == key) return t;
t = key > t->key? t->right : t->left;
}
return p;
}
Двоичные деревья поиска: свойства
I
Простая процедура вставки
tree * insertNode(tree *t, keytype key, valtype value) {
tree *parent = t;
while (t != NULL) {
parent = t;
if (t->key == key) return; // Уже есть
t = key > t->key? t->right : t->left;
}
tree *node = new tree(key, value);
if (key < parent->key) parent->left = node;
else
parent->right = node;
}
Двоичные деревья поиска: свойства
I
Процедура удаления сложнее, три случая:
1. Нет потомков — удаляем узел у родителя.
2. Один потомок — переставляем узел у родителя на потомка
Двоичные деревья поиска: свойства
I
Процедура удаления сложнее, три случая:
1. Нет потомков — удаляем узел у родителя.
2. Один потомок — переставляем узел у родителя на потомка
3. Два потомка — находим самый левый лист в правом
поддереве и им замещаем удаляемый
Двоичные деревья поиска: свойства
Первый случай: до удаления
10
35
5
3
2
7
4
6
23
94
Двоичные деревья поиска: свойства
Первый случай: после удаления
10
35
5
3
2
7
4
23
94
Двоичные деревья поиска: свойства
Второй случай: до удаления
10
35
5
3
2
7
4
6
23
94
Двоичные деревья поиска: свойства
Второй случай: после удаления
10
35
5
3
2
6
4
23
94
Двоичные деревья поиска: свойства
Третий случай: до удаления
10
35
5
3
2
7
4
6
23
94
Двоичные деревья поиска: свойства
Третий случай: после удаления
23
35
5
3
2
7
4
6
94
Двоичные деревья поиска
Структура хранилища
Двоичное дерево поиска
(наихудшее)
Двоичное дерево поиска
(среднее)
вставка
удаление
поиск
O(N)
O(N)
O(N)
O(log N)
O(log N)
O(log N)
Сбалансированные деревья
поиска
Сбалансированные деревья поиска
I
Задача: реализовать операции с деревьями, имеющие
время в худшем Θ(log N).
H < A · log N + B,
I
где A и B — некоторые фиксированные константы.
Решение:
I
I
использовать сбалансированные деревья;
использовать алгоритмы, не нарушающие
сбалансированность.
Сбалансированные деревья поиска: критерии
сбалансированности
Высота дереве Ht не превосходит A log N + B, если в двоичном
дереве с N узлами выполнено хотя бы одно из условий:
1. для любого узла количество узлов в левом и правом
поддереве Nl , Nr отличаются не более, чем на 1
Nr 6 Nl + 1, Nl 6 Nr + 1
2. для любого узла количество подузлов в левом и правом
поддеревьях удовлетворяют условиям
Nr 6 2Nl + 1, Nl 6 2Nr + 1
3. для любого узла высоты левого и правого поддеревьев
Hl , Hr удовлетворяют условиям
Hr 6 Hl + 1, Hl 6 Hr + 1
Сбалансированные деревья поиска
Случай 1 — идеально сбалансированное дерево.
Пусть Hideal (N) — максимальная высота идеально
сбалансированного дерева.
I
N — нечётно и равно 2M + 1. Тогда левое и правое
поддеревья должны содержать ровно по M вершин.
Hideal (2M + 1) = 1 + Hideal (M)
I
N — чётно и равно 2M. Тогда
Hideal 2M = 2 + max(Hideal (M − 1), Hideal (M))
Так как Hideal (M) — неубывающая функция, то
Hideal (2M) = 1 + Hideal (M)
Hideal (N) 6 log2 N
Сбалансированные деревья поиска
Случай 2. Примерная сбалансированность количества узлов.
Пусть H(M) — максимальная высота сбалансированного дерева
со свойством 2.
I
Тогда H(1) = 0, H(2) = H(3) = 1.
I
При добавлении узла один из узлов будет корнем,
остальные N − 1 распределятся в отношении Nl : Nr , где
Nl + Nr = N − 1.
I
Не умаляя общности, предположим, что Nr > Nl , тогда
Nr 6 2Nl + 1.
H(N) = max (1 + max(H(Nl ), H(Nr )))
Nl ,Nr
Сбалансированные деревья поиска
Функция H(N) — неубывающая, поэтому
H(N) = 1 + H(max(Nr , Nl ))
При ограничениях Nr 6 2Nl + 1 и Nl + Nr = N + 1 получаем
2N − 1
N(H) = 1 + H
3
2N
H(N) > 1 + H
3
H(N) > log3/2 N + 1 ≈ 1.71 log2 N + 1
Сбалансированные деревья поиска
Случай 3. Примерная сбалансированность высот. АВЛ-деревья.
Пусть N(H) — минимальное число узлов в АВЛ-дереве с
высотой H (минимальное АВЛ-дерево).
I
Пусть левое дерево имеет высоту H − 1.
I
Правое дерево будет иметь высоту H − 1 или H − 2.
I
N(H) — неубывающая, для минимального АВЛ-дерева
высота правого равна H − 2.
I
Число узлов в минимальном АВЛ-дереве:
N(H) = 1 + N(H − 1) + N(H − 2)
N(h + 1)
=ϕ=
lim
h→∞
N(h)
√
5+1
2
H(N) ≈ logϕ (N − 1) + 1 ≈ 1.44 log2 N + 1
Quiz
http://rbtsv.ru/quiz/index
Красно-чёрные деревья.
Красно-чёрные деревья
Красно-чёрное дерево это двоичное дерево поиска.
I
Вершины разделены на красные и чёрные.
I
Каждая вершина хранит поля ключ и значение.
I
Каждая вершина имеет указатель left, right, parent
I
Отсутствующие указатели помечаются указателями на
фиктивный узел nil
I
Каждый лист nil — чёрный
I
Если вершина — красная, то её потомки — чёрные
I
Все пути от корня root к листьям содержат одинаковое
число чёрных вершин. Это число называется чёрной
высотой дерева, black height, bh(root)
Красно-чёрные деревья
6
11
4
2
5
1
nil
3
nil
nil
nil
nil
8
nil
13
7
nil
10
nil
9
nil
12
nil
nil
nil
nil
nil
Красно-чёрные деревья
Теорема: красно-чёрное дерево с N внутренними листьями
имеет высоту не более log2 (N + 1)
I
Для листьев чёрная высота равна нулю.
I
Докажем, что |Tx | >= 2bh(x) .
I
База индукции: Пусть вершина x является листом. Тогда
bh(x) = 0 и |T (x)| = 0 < 2bh(x)
I
Пусть вершина x не является листом и bh(x) = k. Тогда
для обоих потомков bh(l) > k − 1, bh(r ) > k − 1, т. к.
красный будет иметь высоту k, чёрный — k − 1.
I
По предположению индукции
|Tl |, |Tr | >= 2k−1 → |Tk | = |Tl | + |Tr | >= 2k − 1
Красно-чёрные деревья
I
По свойству (3) не менее половины узлов составляют
чёрные вершины.
I
bh(t) > H/2
I
N > 2H/2 − 1
H 6 2 · log2 N + 1
Красно-чёрные деревья: операция вставки
I
При обычной вставке свойства красно-чёрности могут
нарушаться.
I
Для изменения структуры применяются операции
поворота деревьев.
I
Для изменения красно-чёрности применяется
корректировка.
I
Для удобства полагаем, что для дерева имеется узел nil
Красно-чёрные деревья: структуры данных
struct tree {
struct tnode *root, *nil;
tree();
~tree() { delete nil; }
};
struct tnode {
tnode *left, *right, *parent;
bool black;
mydata data;
tnode(tree *t) {
left = right = parent = t->nil;
}
};
tree::tree() {
nil = new tnode(); nil->black = true;
};
Красно-чёрные деревья: повороты
Для поддержания сбалансированности вводится операция
вращение или поворот.
Для этого отцепляется поддерево и переносится на другую
сторону.
A
Left
Center
B
B
A
Right
Left
Right
Center
Левый поворот дерева.
Красно-чёрные деревья: повороты
Код левого поворота:
void rotate_left(tree *t, tnode *x) { // Поворот в узле x
assert(x->right != t->nil);
tnode *y = x->right;
x->right = y->left;
if (y->left != root->nil) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == root->nil) t->root = y; // новый корень
else {
if (x == x->parent->left) x->parent->left = y;
else
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
Красно-чёрные деревья: повороты
A
B
Left
B
Right
Center
Left
A
Center
Правый поворот дерева.
Right
Красно-чёрные деревья: вставка
I
Вставляем почти как в обычное двоичное дерево поиска.
I
Красим узел в красный цвет
I
Корректируем дерево для сохранения красно-чёрности.
Красно-чёрные деревья: вставка
void tree_insert(tree *t, tnode *z) {
tree *y = t->nil; tree *x = t->root;
while (x != t->nil) {
y = x;
if (z->key < x->key) x = x->left;
else
x = x->right;
}
z->parent = y;
if (y == t->nil) t->root = z;
else {
if (z->key < y->key) y->left = z;
else
y->right = z;
}
z->left = z->right = t->nil;
z->black = false;
insert_fixup(t, z);
}
Красно-чёрные деревья: коррекция
void insert_fixup(tree *t, tnode *z) {
while(!z->parent->black) {
if (z->parent == z->parent->parent->left) {
tnode *y = z->parent->parent->right;
if (!y->black) {
z->parent->black = true;
y->black = true;
z->parent->parent->black = false;
z = z->parent->parent;
} else {
if (z == z->parent->right) {
z = z->parent;
rotate_left(t, z);
z->parent->black = true;
z->parent->parent->black = false;
rotate_right(t, z->parent->parent);
}
} else ... left <-> right
}
t->root->black = true;
}
Красно-чёрные деревья
Вставка 4, корректирование
11
14
2
1
5
Смена цветов
15
7
z
4
8 y
Красно-чёрные деревья
Поворот
Вставка 4, корректирование
11
14
2
1
7
5
y
15
z
8
4
11
14
7
z
8
2
1
5
4
y
15
Красно-чёрные деревья
Заключительная коррекция
7
11
z
2
8
1
5
4
14
15
Абстракция приоритетная
очередь
Приоритетная очередь
I
Приоритетная очередь (priorityqueue) — очередь, элементы
которой имеют приоритет.
I
После вставки элемента очередь остаётся упорядоченном
по приоритету состоянии
I
Первым извлекается наиболее приоритетный элемент
(максимум или минимум).
Интерфейс абстракции:
I
insert — добавление элемента из очереди
I
extractMin(Max) — извлекает самый приоритетный
элемент
I
fetchMin(Max) — получает самый приоритетный элемент
I
increasePriority — изменяет приоритет элемента
I
merge — сливает очереди
Приоритетная очередь
Пример очереди:
Значение (value)
Москва
Казань
Урюпинск
Малиновка
Приоритет (priority)
12000000
1500000
10000
200
Приоритетная очередь:представление
I
Бинарная куча — двоичное дерево, удовлетворяющее
условиям:
I
I
Для любой вершины её приоритет не меньше (больше)
приоритета потомков.
Дерево является полным двоичным.
Другое название — пирамида (heap)
Приоритетная очередь
I
Невозрастающая пирамида
50
20
14
6
45
17
10
5
4
Приоритетная очередь
I
Неубывающая пирамида
3
6
11
96
5
23
17
16
9
Приоритетная очередь:реализация
50
20
14
6
45
17
5
4
10
Хранение в виде массива с индексами от 1 до N:
50 20 45 14 17 5 4 6 10
I
Индекс корня дерева всегда 1 — максимальный
(минимальный) элемент
I
Индекс родителя узла i — b 2i c
I
Индекс левого потомка узла i — 2i
I
Индекс правого потомка узле i — 2i + 1
Приоритетная очередь
I
Реализация на базе массива.
struct bhnode { // Узел
string data;
int priority;
};
struct binary_heap {
bhnode *body;
int
bodysize;
int
numnodes;
binary_heap(int maxsize);
...
};
Бинарная куча
I
Создание бинарной кучи
binary_heap::binary_heap(int maxsize) {
body = new bhnode[maxsize+1];
bodysize = maxsize;
numnodes = 0;
}
~binary_heap::binary_heap() {
delete body;
}
void binary_heap::swap(int a, int b) {
bhnode temp = body[a];
body[a] = body[b];
body[b] = temp;
}
Tcreate = O(1)
Бинарная куча: поиск минимума(максимума)
I
Поиск в min-heap:
bhnode *binary_heap::fetchMin() {
return numnodes == 0? 0 : body + 1;
}
TfetchMin = O(1)
Бинарная куча: вставка элемента
I
Этап 1. Вставка в конец кучи.
Вставка элемента 33
(1)
(2)
(4)
(8)
5
45
17
(3)
(5)
(9)
4
50
(10)
14
(6)
20
10
(7)
33
Отлично! Структура кучи не испортилась!
50 45 20 17 14 10 6 5 4 33
6
Бинарная куча: вставка элемента
I
Этап 2. Корректировка значений.
Вставка элемента 33
(1)
(2)
(4)
(8)
5
45
17
(3)
(5)
(9)
4
50
(10)
33
(6)
20
10
14
Куча удовлетворяет всем условиям.
50 45 20 17 33 10 6 5 4 14
(7)
6
Бинарная куча: вставка элемента
I
Попытаемся вставить максимальный элемент.
Вставка элемента 70
(1)
(2)
(4)
(8)
5
45
17
(3)
(5)
(9)
4
50
(10)
14
(6)
70
50 45 20 17 14 10 6 5 4 70
20
10
(7)
6
Бинарная куча: вставка элемента
I
Максимальный элемент ползёт вверх по дереву.
Вставка элемента 70
(1)
(2)
(4)
(8)
5
45
17
(3)
(5)
(9)
4
50
(10)
70
(6)
14
50 45 20 17 70 10 6 5 4 14
20
10
(7)
6
Бинарная куча: вставка элемента
I
Максимальный элемент ползёт вверх по дереву.
Вставка элемента 70
(1)
(2)
(4)
(8)
5
70
17
(3)
(5)
(9)
4
50
(10)
45
(6)
14
50 70 20 17 45 10 6 5 4 14
20
10
(7)
6
Бинарная куча: вставка элемента
I
Максимальный элемент ползёт вверх по дереву.
Вставка элемента 70
(1)
(2)
(4)
(8)
5
50
17
(3)
(5)
(9)
4
70
(10)
45
(6)
14
70 50 20 17 45 10 6 5 4 14
20
10
(7)
6
Бинарная куча: вставка элемента
I
Реализация.
int binary_heap::insert(bhnode node) {
if (numnodes > bodysize) {
return -1; // или расширяем.
}
body[++numnodes] = node;
for (int i = numnodes; i > 1 &&
body[i].priority > body[i/2].priority;
i /= 2) {
swap(i, i/2);
}
}
TInsert = O(log N)
Бинарная куча: удаление максимального (минимального)
I
Обмен с последним
Удаление максимального
(1)
(2)
(4)
(8)
50
(3)
17
(5)
(9)
5
4
(10)
(4)
(8)
5
(3)
(5)
(9)
4
(10)
(7)
10
6
14
50
17
(6)
45
20
14
(1)
(2)
70
45
(6)
20
10
(7)
6
14
Свойства кучи нарушены. Требуется восстановление.
Бинарная куча: восстановление свойств
I
Для восстановления свойств применяем функцию heapify .
void binary_heap::heapify(int index) {
for (;;) {
int left = index + index; int right = left + 1;
// Кто больше, [index], [left], [right]?
int largest = index;
if (left <= numnodes &&
body[left].priority > body[index].priority)
largest = left;
if (right <= numnodes &&
body[right].priority > body[largest].priority)
largest = right;
if (largest == index) break;
swap(index, largest);
index = largest;
}
}
Theapify = O(log N)
Бинарная куча: восстановление свойств
I
Восстановление индекса (1)
Heapify(index)
Max([index],[left],[right]) = [left]
(1)
(2)
(4)
(8)
5
17
50
(3)
(left)
(5)
(9)
14
(index)
45
(6)
10
20
(right)
(7)
6
4
14 50 20 17 45 10 6 5 4
Новый индекс для восстановления (2)
Бинарная куча: восстановление свойств
I
Восстановление индекса (2)
Heapify(index)
(1)
(2)
(4)
17
(left)
14
50
(index)
(index)
(5)
45
(3)
(6)
10
20
(right)
(7)
6
(right)
(8)
5
(9)
4
Max([index],[left],[right]) = [right]
50 14 20 17 45 10 6 5 4
Новый индекс для восстановления (5)
Бинарная куча: восстановление свойств
I
Восстановление индекса (5)
Heapify(index)
(1)
(2)
(4)
17
50
(index)
45
(3)
(5)
14
(6)
10
(index)
(8)
5
(9)
4
Max([index],[left],[right]) = [right]
50 45 20 17 14 10 6 5 4
Восстановление закончено.
20
(right)
(7)
6
Бинарная куча: увеличение (уменьшение) приоритета
элемента
I
Для max-heap при увеличении приоритета элемент может
ползти только вверх.
int binary_heap::increasePriority(int index, int priority) {
if (body[index].priority >= priority)
return -1;
for (body[index].priority = priority;
index > 1
&& body[index].priority > body[index/2].priority;
index /= 2) {
swap(index, index/2);
}
return index;
}
TincreasePriority = O(log N)
Бинарная куча
Бинарная куча — хороший выбор для представления
абстракций множество и отображение.
HeapSort
HeapSort
I
На основе бинарной кучи можно реализовать алгоритм
сортировки со сложностью O(N log N) в худшем случае.
I
Как?
HeapSort
I
На основе бинарной кучи можно реализовать алгоритм
сортировки со сложностью O(N log N) в худшем случае.
I
Как?
I
Является ли отсортированным массив, являющийся
представлением бинарной кучи?
HeapSort
I
На основе бинарной кучи можно реализовать алгоритм
сортировки со сложностью O(N log N) в худшем случае.
I
Как?
I
Является ли отсортированным массив, являющийся
представлением бинарной кучи?
I
Нет.
I
Кто виноват? Что делать?
HeapSort
I
Нужно скомбинировать методы бинарной кучи.
1. Создать бинарную кучу.
2. Вставить в неё элементы массива
3. Извлекать из неё максимальный (минимальный) элемент с
удалением.
HeapSort
I
Примерный код сортировки HeapSort
struct bhnode { // Узел
int priority;
};
void heapsort(int v[], int vsize) {
binary_heap *h = new binary_heap(vsize);
for (int i = 0; i < vsize; i++) {
bhnode b; b.priority = v[i];
h->insert(b);
}
for (int i = 0; i < vsize; i++) {
v[i] = h->extractMin()->priority;
}
delete h;
}
HeapSort
I
Сложность алгоритма:
1. Создание бинарной кучи — T1 = O(1).
2. Вставка N элементов — T2 = O(N log N).
3. Извлечение удалением N элементов — T3 = O(N log N).
Theapsort = T1 +T2 +T3 = O(1)+O(N log N)+O(N log N) = O(NlogN)
HeapSort
Сложность операций.
I
insert — O(log N)
I
extractMin(Max) — O(log N)
I
fetchMin(Max) — O(1)
I
increasePriority — O(log N)
I
merge — O(N log N)
Спасибо за внимание.
Следующая лекция —
Хеш-таблицы.
Автор
tekhnostrim
Документ
Категория
Без категории
Просмотров
83
Размер файла
888 Кб
Теги
лекция
1/--страниц
Пожаловаться на содержимое документа