Бинарные кучи (пирамиды)

Бинарные кучи (пирамиды) Лекция 9 Очередь с приоритетом (priority queue) ▪ Очередь с приоритетом (priority queue) – очередь, в которой элементы имеют приоритет (вес); первым извлекается элемент с наибольшим приоритетом (ключом) ▪ Поддерживаемые операции:  Insert – добавление элемента в очередь  Max – возвращает элемент с максимальным приоритетом  ExtractMax – удаляет из очереди элемент с максимальным приоритетом  IncreaseKey – изменяет значение приоритета заданного элемента  Merge – сливает две очереди в одну Значение (value) Приоритет (priority) Слон 3 Кит 1 Лев 15 Бинарная куча – пирамида (binary heap) ▪ Бинарная куча (пирамида, сортирующее дерево, binary heap) – это двоичное дерево, удовлетворяющее следующим условиям:  Приоритет любой вершины не меньше ( ≥ ), приоритета ее потомков  Дерево является полным двоичным деревом (complete binary tree) – все уровни заполнены слева направо (возможно за исключением последнего) Бинарная куча – пирамида (binary heap) Невозрастающая пирамида max-heap Неубывающая пирамида min-heap Приоритет любой вершины не меньше (≥), приоритета потомков Приоритет любой вершины не больше (≤), приоритета потомков Реализация бинарной кучи на основе массива 16 max-heap (10 элементов) 14 10 8 7 4 2 9 3 1 Массив 𝑯[𝟏. . 𝟏𝟒] приоритетов (ключей): 16 14 10 8 ▪ ▪ ▪ ▪ 7 9 3 2 4 1 Корень дерева хранится в ячейке 𝐻[1] – максимальный элемент Индекс родителя узла 𝑖: 𝑃𝑎𝑟𝑒𝑛𝑡 𝑖 = 𝑖/2 𝐻 𝑃𝑎𝑟𝑒𝑛𝑡 𝑖 ≥ 𝐻[𝑖] Индекс левого дочернего узла: 𝐿𝑒𝑓𝑡 𝑖 = 2𝑖 Индекс правого дочернего узла: 𝑅𝑖𝑔ℎ𝑡 𝑖 = 2𝑖 + 1 Реализация бинарной кучи на основе массива struct heapnode { int key; char *value; }; /* Priority (key) */ /* Data */ struct heap { int maxsize; int nnodes; struct heapnode *nodes; }; /* Array size */ /* Number of keys */ /* Nodes: [0..maxsize] */ Создание пустой кучи 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; } } TCreate = O(1) return h; Удаление кучи 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; Поиск максимального элемента 16 max-heap (10 элементов) 14 10 8 7 4 2 9 Максимальный элемент хранится в корне max-heap 3 1 Массив 𝑯[𝟏. . 𝟏𝟒] приоритетов (ключей): 16 14 10 8 ▪ ▪ ▪ ▪ 7 9 3 2 4 1 Корень дерева храниться в ячейке 𝐻[1] – максимальный элемент Индекс родителя узла 𝑖: 𝑃𝑎𝑟𝑒𝑛𝑡 𝑖 = 𝑖/2 𝐻 𝑃𝑎𝑟𝑒𝑛𝑡 𝑖 ≥ 𝐻[𝑖] Индекс левого дочернего узла: 𝐿𝑒𝑓𝑡 𝑖 = 2𝑖 Индекс правого дочернего узла: 𝑅𝑖𝑔ℎ𝑡 𝑖 = 2𝑖 + 1 Поиск максимального элемента struct heapnode *heap_max(struct heap *h) { if (h->nnodes == 0) return NULL; return &h->nodes[0]; TMax = O(1) } Вставка элемента в бинарную кучу (maxheap) 11 > 5 11 > 9 Вставка элемента с приоритетом 11 [DSABook, Глава 12] TInsert = O(logn) Вставка элемента в бинарную кучу 15 nodes[nnodes] = 15 15 > 7 => swap(15, 7) 15 > 14 => swap(15, 14) 15 < 16 15 15 Вставка элемента с приоритетом 15 [CLRS, Глава 6] Вставка элемента в бинарную кучу Вставка элемента [DSABook, Глава 12] Вставка элемента в бинарную кучу int heap_insert(struct heap *h, int key, char *value) { if (h->nnodes >= h->maxsize) { /* Heap overflow */ return -1; } h->nnodes++; h->nodes[h->nnodes].key = key; h->nodes[h->nnodes].value = strdup(value); } // HeapifyUp for (int i = h->nnodes; i > 1 && h->nodes[i].key > h->nodes[i / 2].key; i = i / 2) { heap_swap(&h->nodes[i], &h->nodes[i / 2]); } return 0; T = O(logn) Insert Удаление максимального элемента Заменяем корень 𝐴[0] листом 𝐴[𝑛] 𝐻𝑒𝑎𝑝𝑖𝑓𝑦𝐷𝑜𝑤𝑛(𝐴, 1) 5<9 Удаление элемента с максимальным приоритетом 11 [DSABook, Глава 12] Удаление максимального элемента HeapifyDown(A, 1) 5<9 Удаление максимального элемента struct heapnode heap_extract_max(struct heap *h) { if (h->nnodes == 0) return (struct heapnode){0, NULL}; struct heapnode maxnode = h->nodes[0]; h->nodes[0] = h->nodes[h->nnodes]; h->nnodes--; heap_heapify(h, 0); } return maxnode; Восстановление свойств кучи (max-heap) 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) Увеличение ключа в maxheap TIncrease = O(logn) Увеличение ключа в maxheap 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 ▪ Требуется построить из его элементов бинарную кучу Построение бинарной кучи ▪ Дан неупорядоченный массив A длины n ▪ Требуется построить из его элементов бинарную кучу function BuildHeap(A[0:n-1]) h = CreateBinaryHeap(n) // O(1) for i = 0 to n-1 do HeapInsert(h, A[i], A[i]) end for end function // O(logn) TBuildHeap = O(nlogn) Построение кучи из массива за время 𝑂(𝑛) ▪ Дан неупорядоченный массив A длины n ▪ Требуется построить из его элементов бинарную кучу ▪ A[6] = (3, 7, 9, 6, 8, 4) ▪ BuildMaxHeap(A, 6) int main() { struct heap *h; struct heapnode node; h = heap_create(100); heap_insert(h, 16, "16"); heap_insert(h, 14, "14"); heap_insert(h, 10, "10"); heap_insert(h, 8, "8"); heap_insert(h, 7, "7"); heap_insert(h, 9, "9"); heap_insert(h, 3, "3"); heap_insert(h, 2, "2"); heap_insert(h, 4, "4"); heap_insert(h, 1, "1"); Работа с бинарной кучей node = heap_extract_max(h); printf("Item: %d\n", node.key); int i = heap_increase_key(h, 9, 100); } heap_free(h); return 0; Сортировка на базе бинарной кучи ▪ На основе бинарной кучи можно реализовать алгоритм сортировки с вычислительной сложностью 𝑂(𝑛𝑙𝑜𝑔𝑛) в худшем случае Как ? Сортировка на базе бинарной кучи ▪ На основе бинарной кучи можно реализовать алгоритм сортировки с вычислительной сложностью 𝑂(𝑛𝑙𝑜𝑔𝑛) в худшем случае Как ? function HeapSort(v[0:n-1]) h = CreateBinaryHeap(n) for i = 0 to n-1 do HeapInsert(h, v[i], v[i]) T1 = O(1) T2 = O(logn) end for for i = 0 to n-1 do v[i] = HeapRemoveMax(h) end for end function T3 = O(logn) Сортировка на базе бинарной кучи ▪ На основе бинарной кучи можно реализовать алгоритм сортировки с вычислительной сложностью 𝑂(𝑛𝑙𝑜𝑔𝑛) в худшем случае Как ? function HeapSort(v[0:n-1]) h = CreateBinaryHeap(n) for i = 0 to n-1 do HeapInsert(h, v[i], v[i]) T1 = O(1) T2 = O(logn) end for for i = 0 to n-1 do v[i] = HeapRemoveMax(h) end for end function T3 = O(logn) THeapSort = 1 + nlogn + nlogn = O(nlogn) Сортировка на базе бинарной кучи ▪ На основе бинарной кучи можно реализовать алгоритм сортировки с вычислительной сложностью 𝑂(𝑛𝑙𝑜𝑔𝑛) в худшем случае Как ? Очередь с приоритетом (priority queue) ▪ В таблице приведены трудоемкости операций очереди с приоритетом (в худшем случае) ▪ Символом ‘*’ отмечена амортизированная сложность операций Операция Binary heap Binomial heap Fibonacci heap Pairing heap Brodal heap FindMin Θ(1) 𝑂(𝑙𝑜𝑔𝑛) Θ(1) Θ(1) ∗ Θ(1) DeleteMin Θ(𝑙𝑜𝑔𝑛) Θ(𝑙𝑜𝑔𝑛) Insert Θ(𝑙𝑜𝑔𝑛) 𝑂(𝑙𝑜𝑔𝑛) Θ(1) Θ(1) ∗ Θ(1) DecreaseKey Θ(𝑙𝑜𝑔𝑛) Θ(𝑙𝑜𝑔𝑛) Θ(1) ∗ 𝑂(𝑙𝑜𝑔𝑛) ∗ Θ(1) Merge/Union Θ(𝑛) Ω(𝑙𝑜𝑔𝑛) Θ(1) Θ(1) ∗ Θ(1) 𝑂(𝑙𝑜𝑔𝑛) ∗ 𝑂(𝑙𝑜𝑔𝑛) ∗ 𝑂(𝑙𝑜𝑔𝑛) Литература ▪ [DSABook, Глава 12] ▪ Анализ вычислительной сложности построения бинарной кучи (Build-Max-Heap) за время 𝑂(𝑛) [CLRS, Глава 6]