Двоичная куча – пирамида (binary heap)

Сентябрь 5, 2022

Главная
Алгебра
Двоичная куча – пирамида (binary heap)

Содержание

2. Двоичная куча – пирамида (binary heap) Двоичная куча (пирамида, сортирующее дерево, binary heap) – это двоичное
3. История появления Бинарная куча была Джоном Уильямом Джозефом Уильямсом в 1964 году как структура данных для
4. Двоичная куча Приоритет в любой вершине не меньше, чем приоритет её потомков Глубина всех листьев (расстояние
5. Бинарная куча – пирамида (binary heap) 4 Невозрастающая пирамида max-heap Приоритет любой вершины не меньше (≥),
6. Реализация бинарной кучи на основе массива 5 7 8 2 4 1 9 3 14 10
7. Реализация бинарной кучи на основе массива /* Priority (key) */ /* Data */ struct heapnode {
8. Поиск максимального элемента 9 7 8 2 4 1 9 3 14 10 16 max-heap (10
9. Вставка элемента в бинарную кучу 11 15 15 15 nnodes++; nodes[nnodes] = 15 15 15 >
10. Вставка элемента в бинарную кучу void addelem(int n) { int i, parent; i = HeapSize; h[i]
11. Поиск максимального элемента 10 struct heapnode *heap_max(struct heap *h) { if (h->nnodes == 0) return NULL;
12. Удаление максимального элемента Заменяем корень листом Восстанавливаем свойства кучи heap_heapify(H, 1)
13. Удаление максимального элемента struct heapnode heap_extract_max(struct heap *h) { if (h->nnodes == 0) return (struct heapnode){0,
14. Удаление максимального элемента int getmax() { int x; x = h[0]; h[0] = h[HeapSize-1]; HeapSize--; heapify(0);
15. struct heap *heap_create(int maxsize) { struct heap *h; h = malloc(sizeof(*h)); if (h != NULL) {
16. void heap_free(struct heap *h) { free(h->nodes); free(h); } void heap_swap(struct heapnode *a, struct heapnode *b) {
17. Восстановление свойств кучи (max-heap) 5 1 void heap_heapify(struct heap *h, int index) { for (;;) {
18. int main() { struct heap *h; struct heapnode node; h = heap_create(100); node = heap_extract_max(h); printf("Item:
19. Изменение кучи
20. Увеличение ключа int heap_increase_key(struct heap *h, int index, int key) { if (h->nodes[index].key > key) return
21. Построение бинарной кучи Дан неупорядоченный массив A длины n Требуется построить из его элементов бинарную кучу
22. Построение бинарной кучи (v1) Дан неупорядоченный массив A длины n Требуется построить из его элементов бинарную
23. Построение бинарной кучи (v2) 23 Дан неупорядоченный массив A длины n Требуется построить из его элементов
24. Использование двоичной кучи
25. Очередь с приоритетом (priority queue) Очередь с приоритетом (priority queue) – очередь, в которой элементы имеют
26. Сравнение оценки алгоритмов В таблице приведены трудоемкости операций очереди с приоритетом (в худшем случае, worst case)
27. Алгоритм Дейкстры Обозначим через n количество вершин, а через m — количество рёбер в графе G.
28. Сортировка на базе бинарной кучи На основе бинарной кучи можно реализовать алгоритм сортировки с вычислительной сложностью
29. Сортировка на базе бинарной кучи На основе бинарной кучи можно реализовать алгоритм сортировки с вычислительной сложностью
30. Сортировка на базе бинарной кучи На основе бинарной кучи можно реализовать алгоритм сортировки с вычислительной сложностью
31. Оценки работы алгоритма
32. Скорость работы программы
33. Скорость работы программы с выводом данных
34. Отношение
35. Отношение теоретического к практическому
37. Скачать презентацию

Слайд 2

Двоичная куча – пирамида (binary heap)
Двоичная куча (пирамида, сортирующее дерево, binary

heap) – это двоичное дерево, удовлетворяющее следующим условиям:
Приоритет любой вершины не меньше ( ≥ ), приоритета ее потомков
Дерево является полным двоичным деревом
(complete binary tree) – все уровни заполнены слева направо (возможно за исключением последнего)

Слайд 3

История появления
Бинарная куча была Джоном Уильямом Джозефом Уильямсом в 1964 году

как структура данных для heapsort(пирамидальной сортровки).
Но наибольшего применения достигла лишь в 1990-х годах, в эпоху повсеместного использования компьютеров. В том числе двоичную кучу существенно популяризировал Чарльз Лейзерсон, который также использовал её в разработке собственного языка программирования Clik.

Слайд 4

Двоичная куча
Приоритет в любой вершине не меньше, чем приоритет её потомков
Глубина

всех листьев (расстояние до корня) отличается не более чем на 1 слой.
Последний слой заполняется слева направо без «дырок».

Слайд 5

Бинарная куча – пирамида (binary heap)
4
Невозрастающая пирамида max-heap
Приоритет любой вершины не

меньше (≥),
приоритета потомков

Неубывающая пирамида min-heap
Приоритет любой вершины
не больше (≤),

приоритета потомков

max

min

Слайд 6

Реализация бинарной кучи на основе массива
5
7
8
2 4 1
9
3
14
10
16
max-heap (10 элементов)
Массив H[1..14] приоритетов (ключей):
?/2
=

Корень дерева храниться в ячейке ?[1] – максимальный элемент
Индекс родителя узла i: ?????? ? =
Индекс левого дочернего узла: ???? ?
Индекс правого дочернего узла: ???ℎ? ? = 2? + 1
? ?????? ? ≥ ?[?]

Слайд 7

Реализация бинарной кучи на основе массива
/* Priority (key) /
/ Data */
struct

heapnode { int key;
char *value;
};

/* Размер массива*/
/* Номер ключа*/
/* Nodes: [0..maxsize] */

struct heap {
int maxsize; int nnodes;
struct heapnode *nodes;
};

Слайд 8

Поиск максимального элемента
9
7
8
2 4 1
9
3
14
10
16
max-heap (10 элементов)
Массив H[1..14] приоритетов (ключей):
Максимальный
элемент хранится в корне

max-heap

?/2
= 2?

Слайд 9

Вставка элемента в бинарную кучу
11
15
15
15
nnodes++;
nodes[nnodes] = 15
15 < 16
15 > 7

=> swap(15, 7)
15 > 14 => swap(15, 14)
Вставка элемента с приоритетом 15

Слайд 10

Вставка элемента в бинарную кучу
void addelem(int n) {
int i, parent;

i = HeapSize;
h[i] = n;
parent = (i-1)/2;
while(parent >= 0 && i > 0) {
if(h[i] > h[parent]) {
int temp = h[i];
h[i] = h[parent];
h[parent] = temp;
}
i = parent;
parent = (i-1)/2;
}
HeapSize++;
}

TInsert = O(logn)

Слайд 11

$Поиск максимального элемента 10 struct heapnode heap_max(struct heap h) { if$

Поиск максимального элемента
10
struct heapnode heap_max(struct heap h)
{
if (h->nnodes == 0)
return NULL;
return

&h->nodes[1];
}

TMax = O(1)

Слайд 12

Удаление максимального элемента
Заменяем
корень листом
Восстанавливаем свойства кучи heap_heapify(H, 1)

Слайд 13

$Удаление максимального элемента struct heapnode heap_extract_max(struct heap *h) { if (h->nnodes$

Удаление максимального элемента
struct heapnode heap_extract_max(struct heap *h)
{
if (h->nnodes == 0)
return (struct

heapnode){0, NULL};
struct heapnode maxnode = h->nodes[1]; h->nodes[1] = h->nodes[h->nnodes];
h->nnodes--;
heap_heapify(h, 1);
return maxnode;
}

Слайд 14

Удаление максимального элемента
int getmax() {
int x;
x = h[0];
h[0]

= h[HeapSize-1];
HeapSize--;
heapify(0);
return(x);
}
};

Слайд 15

$struct heap heap_create(int maxsize) { struct heap h; h = malloc(sizeof(*h));$

struct heap heap_create(int maxsize)
{
struct heap h;
h = malloc(sizeof(*h));
if (h != NULL)

{
h->maxsize = maxsize; h->nnodes = 0;
/* Heap nodes [0, 1, ..., maxsize] */
h->nodes = malloc(sizeof(*h->nodes) * (maxsize + 1));
if (h->nodes == NULL) { free(h);
return NULL;
}
}

return h;

}

Создание пустой кучи

TCreate = O(1)

Слайд 16

$void heap_free(struct heap *h) { free(h->nodes); free(h); } void heap_swap(struct heapnode$

void heap_free(struct heap h)
{
free(h->nodes); free(h);
}
void heap_swap(struct heapnode a,
struct heapnode *b)
{
struct heapnode

temp;
temp = *a;
*a = *b;
*b = temp;

}

Удаление кучи

Слайд 17

Восстановление свойств кучи (max-heap)
5
1
void heap_heapify(struct heap *h, int index)
{
for (;;) {
int

left = 2 * index;
int right = 2 * index + 1;
// Find largest key: A[index], A[left] and A[right]
int largest = index;
if (left <= h->nnodes &&
h->nodes[left].key > h->nodes[index].key)
{ largest = left; }
if (right <= h->nnodes &&
h->nodes[right].key > h->nodes[largest].key)
{ largest = right; }
if (largest == index)
break;
heap_swap(&h->nodes[index], &h->nodes[largest]); index = largest;

}

THeapify = O(logn)

Слайд 18

int main()
{
struct heap *h;
struct heapnode node;
h = heap_create(100);
node = heap_extract_max(h); printf("Item:

%d\n", node.key);
return 0;
}

Работа с бинарной кучей

Слайд 19

Изменение кучи

Слайд 20

$Увеличение ключа int heap_increase_key(struct heap *h, int index, int key) {$

Увеличение ключа
int heap_increase_key(struct heap *h, int index, int key)
{
if (h->nodes[index].key >

key)
return -1;
h->nodes[index].key = key;
for ( ; index > 1 &&
h->nodes[index].key > h->nodes[index / 2].key; index = index / 2)
{
heap_swap(&h->nodes[index], &h->nodes[index / 2]);
}
return index;
}

TIncrease = O(logn)

Слайд 21

Построение бинарной кучи
Дан неупорядоченный массив A длины n
Требуется построить из его

элементов бинарную кучу

Слайд 22

Построение бинарной кучи (v1)
Дан неупорядоченный массив A длины n
Требуется построить из

его элементов бинарную кучу
function BuildHeap(A[1:n])

end

Слайд 23

Построение бинарной кучи (v2)
23
Дан неупорядоченный массив A длины n
Требуется построить из

его элементов бинарную кучу

function MaxHeapify(A[1:n], i)

// left sub heap
// right sub heap

left = 2 * i right = 2 * i + 1 largest = i

if left <= n and A[left] > A[i] then
largest = left
if right <= n and A[right] > A[largest] then
largest = right
if largest != i then heap_swap(A[i], A[largest]) MaxHeapify(A, largest)
end if end function

// O(1)

// O(h)

function BuildMaxHeap(A[1:n]) h = CreateBinaryHeap(n) for i = ⌊n / 2⌋ downto 1 do
MaxHeapify(A, i)
end function

TBuildHeap = O(n)

Слайд 24

Использование двоичной кучи

Слайд 25

Очередь с приоритетом (priority queue)
Очередь с приоритетом (priority queue) –
очередь, в

которой элементы имеют приоритет (вес);
первым извлекается элемент с наибольшим приоритетом (ключом)
Поддерживаемые операции:
Insert – добавление элемента в очередь
Max – возвращает элемент с максимальным приоритетом
ExtractMax – удаляет из очереди элемент с максимальным приоритетом
IncreaseKey – изменяет значение приоритета заданного элемента
Merge – сливает две очереди в одну

Слайд 26

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

худшем случае, worst case)
Символом ‘*’ отмечена амортизированная сложность операций

Слайд 27

Алгоритм Дейкстры
Обозначим через n количество вершин, а через m — количество рёбер в графе G.
В обычном

простейшем случае получаем O(n*n).
С помощью двоичной кучи сложность алгоритма получается:
О(log n * (n + m)).
Так как время удаления вершины из станет log n при том, что время модификации тоже возрастёт до log n. Так как цикл выполняется порядка n раз, а количество релаксаций (смен меток) не больше m, О(log n * (n + m)).

Слайд 28

Сортировка на базе бинарной кучи
На основе бинарной кучи можно реализовать алгоритм

сортировки с вычислительной сложностью O(nlogn)
в худшем случае
Как ?

Слайд 29

Сортировка на базе бинарной кучи
На основе бинарной кучи можно реализовать алгоритм

сортировки с вычислительной сложностью O(nlogn)
в худшем случае
Как ?

function HeapSort(v[1:n]) h = CreateBinaryHeap(n) for i = 1 to n do
HeapInsert(h, v[i], v[i])
end for
for i = 1 to n do
v[i] = HeapRemoveMax(h)
end for end function

T1 = O(1)

T2 = O(logn)

T3 = O(logn)

Слайд 30

Сортировка на базе бинарной кучи
На основе бинарной кучи можно реализовать алгоритм

сортировки с вычислительной сложностью O(nlogn)
в худшем случае
Как ?

function HeapSort(v[1:n]) h = CreateBinaryHeap(n) for i = 1 to n do
HeapInsert(h, v[i], v[i])
end for
for i = 1 to n do
v[i] = HeapRemoveMax(h)
end for end function

T1 = O(1)

T2 = O(logn)

T3 = O(logn)

THeapSort = 1 + nlogn + nlogn = O(nlogn)

Слайд 31

Оценки работы алгоритма

Слайд 32

Скорость работы программы

Слайд 33

Скорость работы программы с выводом данных

Слайд 34

Отношение

Слайд 35

Двоичная куча – пирамида (binary heap)

Содержание

Двоичная куча – пирамида (binary heap)Двоичная куча (пирамида, сортирующее дерево, binary

История появленияБинарная куча была Джоном Уильямом Джозефом Уильямсом в 1964 году

Двоичная кучаПриоритет в любой вершине не меньше, чем приоритет её потомковГлубина

Бинарная куча – пирамида (binary heap)4Невозрастающая пирамида max-heapПриоритет любой вершины не

Реализация бинарной кучи на основе массива5782 4 193141016max-heap (10 элементов)Массив H[1..14] приоритетов (ключей):?/2=

Реализация бинарной кучи на основе массива/* Priority (key) *//* Data */struct

Поиск максимального элемента9782 4 193141016max-heap (10 элементов)Массив H[1..14] приоритетов (ключей):Максимальныйэлемент хранится в корне

Вставка элемента в бинарную кучу11151515nnodes++;nodes[nnodes] = 1515 < 1615 > 7

Вставка элемента в бинарную кучуvoid addelem(int n) { int i, parent;

Поиск максимального элемента10struct heapnode *heap_max(struct heap *h){if (h->nnodes == 0)return NULL;return

Удаление максимального элементаЗаменяемкорень листомВосстанавливаем свойства кучи heap_heapify(H, 1)

Удаление максимального элементаstruct heapnode heap_extract_max(struct heap *h){if (h->nnodes == 0)return (struct

Удаление максимального элементаint getmax() { int x; x = h[0]; h[0]

struct heap *heap_create(int maxsize){struct heap *h;h = malloc(sizeof(*h));if (h != NULL)

void heap_free(struct heap *h){free(h->nodes); free(h);}void heap_swap(struct heapnode *a,struct heapnode *b){struct heapnode

Восстановление свойств кучи (max-heap)51void heap_heapify(struct heap *h, int index){for (;;) {int

int main(){struct heap *h;struct heapnode node;h = heap_create(100);node = heap_extract_max(h); printf("Item:

Изменение кучи

Увеличение ключаint heap_increase_key(struct heap *h, int index, int key){if (h->nodes[index].key >

Построение бинарной кучиДан неупорядоченный массив A длины nТребуется построить из его

Построение бинарной кучи (v1)Дан неупорядоченный массив A длины nТребуется построить из

Построение бинарной кучи (v2)23Дан неупорядоченный массив A длины nТребуется построить из

Использование двоичной кучи

Очередь с приоритетом (priority queue)Очередь с приоритетом (priority queue) –очередь, в

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

Алгоритм ДейкстрыОбозначим через n количество вершин, а через m — количество рёбер в графе G.В обычном

Сортировка на базе бинарной кучиНа основе бинарной кучи можно реализовать алгоритм

Сортировка на базе бинарной кучиНа основе бинарной кучи можно реализовать алгоритм

Сортировка на базе бинарной кучиНа основе бинарной кучи можно реализовать алгоритм

Оценки работы алгоритма

Скорость работы программы

Скорость работы программы с выводом данных

Отношение

Отношение теоретического к практическому

Похожие презентации

Двоичная куча – пирамида (binary heap)
Двоичная куча (пирамида, сортирующее дерево, binary

История появления
Бинарная куча была Джоном Уильямом Джозефом Уильямсом в 1964 году

Двоичная куча
Приоритет в любой вершине не меньше, чем приоритет её потомков
Глубина

Бинарная куча – пирамида (binary heap)
4
Невозрастающая пирамида max-heap
Приоритет любой вершины не

Реализация бинарной кучи на основе массива
5
7
8
2 4 1
9
3
14
10
16
max-heap (10 элементов)
Массив H[1..14] приоритетов (ключей):
?/2
=

Реализация бинарной кучи на основе массива
/* Priority (key) /
/ Data */
struct

Поиск максимального элемента
9
7
8
2 4 1
9
3
14
10
16
max-heap (10 элементов)
Массив H[1..14] приоритетов (ключей):
Максимальный
элемент хранится в корне

Вставка элемента в бинарную кучу
11
15
15
15
nnodes++;
nodes[nnodes] = 15
15 < 16
15 > 7

Вставка элемента в бинарную кучу
void addelem(int n) {
int i, parent;

Поиск максимального элемента
10
struct heapnode heap_max(struct heap h)
{
if (h->nnodes == 0)
return NULL;
return

Удаление максимального элемента
Заменяем
корень листом
Восстанавливаем свойства кучи heap_heapify(H, 1)

Удаление максимального элемента
struct heapnode heap_extract_max(struct heap *h)
{
if (h->nnodes == 0)
return (struct

Удаление максимального элемента
int getmax() {
int x;
x = h[0];
h[0]

struct heap heap_create(int maxsize)
{
struct heap h;
h = malloc(sizeof(*h));
if (h != NULL)

void heap_free(struct heap h)
{
free(h->nodes); free(h);
}
void heap_swap(struct heapnode a,
struct heapnode *b)
{
struct heapnode

Восстановление свойств кучи (max-heap)
5
1
void heap_heapify(struct heap *h, int index)
{
for (;;) {
int

int main()
{
struct heap *h;
struct heapnode node;
h = heap_create(100);
node = heap_extract_max(h); printf("Item:

Увеличение ключа
int heap_increase_key(struct heap *h, int index, int key)
{
if (h->nodes[index].key >

Построение бинарной кучи
Дан неупорядоченный массив A длины n
Требуется построить из его

Построение бинарной кучи (v1)
Дан неупорядоченный массив A длины n
Требуется построить из

Построение бинарной кучи (v2)
23
Дан неупорядоченный массив A длины n
Требуется построить из

Очередь с приоритетом (priority queue)
Очередь с приоритетом (priority queue) –
очередь, в

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

Алгоритм Дейкстры
Обозначим через n количество вершин, а через m — количество рёбер в графе G.
В обычном

Сортировка на базе бинарной кучи
На основе бинарной кучи можно реализовать алгоритм

Сортировка на базе бинарной кучи
На основе бинарной кучи можно реализовать алгоритм

Сортировка на базе бинарной кучи
На основе бинарной кучи можно реализовать алгоритм