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

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

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

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

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

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

Реализация бинарной кучи на основе массива
/* Priority (key) */
/* Data */
struct heapnode { int key;
char *value;
};
/* Размер массива*/
/* Номер ключа*/
/* Nodes: [0..maxsize] */
struct heap {
int maxsize; int nnodes;
struct heapnode *nodes;
};

Поиск максимального элемента
9
7
8
2 4 1
9
3
14
10
16
max-heap (10 элементов)
Массив H[1..14] приоритетов (ключей):
Максимальный
элемент хранится в корне max-heap
?/2
= 2?
Корень дерева храниться в ячейке ?[1] – максимальный элемент
Индекс родителя узла i: ?????? ? =
Индекс левого дочернего узла: ???? ?
Индекс правого дочернего узла: ???ℎ? ? = 2? + 1
? ?????? ? ≥ ?[?]

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

Вставка элемента в бинарную кучу
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)

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

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

Удаление максимального элемента
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;
}

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

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)

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;
}
Удаление кучи
8

Восстановление свойств кучи (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)

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;
}
Работа с бинарной кучей

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

Увеличение ключа
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)

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

Построение бинарной кучи (v1)
Дан неупорядоченный массив A длины n
Требуется построить из его элементов бинарную кучу
function BuildHeap(A[1:n])
end

Построение бинарной кучи (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)

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

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

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

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

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

Сортировка на базе бинарной кучи
На основе бинарной кучи можно реализовать алгоритм сортировки с вычислительной сложностью 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)

Сортировка на базе бинарной кучи
На основе бинарной кучи можно реализовать алгоритм сортировки с вычислительной сложностью 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)

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

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

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

Отношение

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