Двоичная куча — различия между версиями
Ильнар (обсуждение | вклад) |
Ильнар (обсуждение | вклад) (→Построение кучи за O(n)) |
||
Строка 90: | Строка 90: | ||
Дан массив <tex>a[0.. n - 1].</tex> Требуется построить <tex>d</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива {{---}} сделать нулевой элемент массива корнем, а дальше по очереди добавить все его элементы в конец кучи и запускать от каждого добавленного элемента <math>\mathrm {siftUp}</math>. Временная оценка такого алгоритма <tex> O(n\log{n})</tex>. Однако можно построить кучу еще быстрее — за <tex> O(n) </tex>. | Дан массив <tex>a[0.. n - 1].</tex> Требуется построить <tex>d</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива {{---}} сделать нулевой элемент массива корнем, а дальше по очереди добавить все его элементы в конец кучи и запускать от каждого добавленного элемента <math>\mathrm {siftUp}</math>. Временная оценка такого алгоритма <tex> O(n\log{n})</tex>. Однако можно построить кучу еще быстрее — за <tex> O(n) </tex>. | ||
− | Представим, что в массиве хранится дерево (<tex>a[0] - </tex> корень, а потомками элемента <tex>a[i]</tex> являются <tex>a[2i+1]...a[2i+d]</tex>). Сделаем <tex> \mathrm {siftDown} </tex> для вершин, имеющих хотя бы одного потомка: от <tex dpi=140>\ | + | Представим, что в массиве хранится дерево (<tex>a[0] - </tex> корень, а потомками элемента <tex>a[i]</tex> являются <tex>a[2i+1]...a[2i+d]</tex>). Сделаем <tex> \mathrm {siftDown} </tex> для вершин, имеющих хотя бы одного потомка: от <tex dpi=140>\dfrac{n}{d}</tex> до <tex>0</tex>,{{---}} так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены. |
{{Лемма | {{Лемма | ||
|statement= На выходе получим искомую кучу. | |statement= На выходе получим искомую кучу. | ||
Строка 123: | Строка 123: | ||
'''for''' i = a.heapSize / 2 '''downto''' 0 | '''for''' i = a.heapSize / 2 '''downto''' 0 | ||
siftDown(i) | siftDown(i) | ||
− | </code> | + | </code> |
===Слияние двух куч=== | ===Слияние двух куч=== |
Версия 23:19, 5 июня 2015
Определение
Определение: |
Двоичная куча или пирамида (англ. Binary heap) — такое двоичное подвешенное дерево, для которого выполнены следующие три условия:
|
Удобнее всего двоичную кучу хранить в виде массива
, у которого нулевой элемент, — элемент в корне, а потомками элемента являются и . Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть , где — количество узлов дерева.Чаще всего используют кучи для минимума (когда предок не больше детей) и для максимума (когда предок не меньше детей).
Двоичные кучи используют, например, для того, чтобы извлекать минимум из набора чисел за
. Они являются частным случаем приоритетных очередей.Базовые процедуры
Восстановление свойств кучи
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры
(просеивание вниз) и (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией . Работа процедуры: если -й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами -й элемент с наименьшим из его сыновей, после чего выполняем для этого сына. Процедура выполняется за время .siftDown
function siftDown(i : int): while 2 * i + 1a.heapSize // heapSize — количество элементов в куче left = 2 * i + 1 // left — левый сын right = 2 * i + 2 // right — правый сын j = left if right a.heapSize and a[right] A[left] j = right if a[i] a[j] break swap(a[i], a[j]) i = j
siftUp
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией
.Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем
function siftUp(i : int): while a[i]a[(i - 1) / 2] // i 0 — мы в корне swap(a[i], a[(i - 1) / 2]) i = (i - 1) / 2
Извлечение минимального элемента
Выполняет извлечение минимального элемента из кучи за время
. Извлечение выполняется в четыре этапа:- Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
- Последний элемент копируется в корень, после чего удаляется из кучи.
- Вызывается для корня.
- Сохранённый элемент возвращается.
int extractMin(): int min = a[0] a[0] = a[a.heapSize - 1] a.heapSize = a.heapSize - 1 siftDown(0) return min
Добавление нового элемента
Выполняет добавление элемента в кучу за время
. Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры .
function insert(key : int): a.heapSize = a.heapSize + 1 a[a.heapSize - 1] = key siftUp(a.heapSize - 1)
Построение кучи за O(n)
Определение: |
-куча — это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно потомков. |
Дан массив Требуется построить -кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива — сделать нулевой элемент массива корнем, а дальше по очереди добавить все его элементы в конец кучи и запускать от каждого добавленного элемента . Временная оценка такого алгоритма . Однако можно построить кучу еще быстрее — за .
Представим, что в массиве хранится дерево (
корень, а потомками элемента являются ). Сделаем для вершин, имеющих хотя бы одного потомка: от до ,— так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены.Лемма: |
На выходе получим искомую кучу. |
Доказательство: |
При вызове | для вершины, ее поддеревья являются кучами. После выполнения эта вершина с ее поддеревьями будут также являться кучей. Значит, после выполнения всех получится куча.
Лемма: | ||||||
Время работы этого алгоритма . | ||||||
Доказательство: | ||||||
Число вершин на высоте в куче из элементов не превосходит . Высота кучи не превосходит . Обозначим за высоту дерева, тогда время построения не превосходит
Докажем вспомогательную лемму о сумме ряда.
| ||||||
Псевдокод алгоритма:
function heapify(): for i = a.heapSize / 2 downto 0 siftDown(i)
Слияние двух куч
Даны две кучи
и , размерами и , требуется объединить эти две кучи.Наивная реализация
Поочередно добавим все элементы из
function merge(a, b : Heap):
while b.heapSize
0
a.insert(b.extractMin())
Реализация с помощью построения кучи
Добавим все элементы кучи
в конец массива , после чего вызовем функцию построения кучи. Процедура выполняется за время .
function merge(a, b : Heap): for i = 0 to b.heapSize - 1 a.heapSize = a.heapSize + 1 a[a.heapSize - 1] = b[i] a.heapify()
Поиск k-ого элемента
Требуется найти
-ый по величине элемент в куче.- Создаем новую кучу, в которой будем хранить пару , где — значение элемента, а — индекс элемента в основном массиве, и добавляем в нее корень кучи.
- Возьмем корень новой кучи и добавим её детей из основной кучи, после чего удалим корень. Проделаем этот шаг раз.
- В корне новой кучи будет находиться ответ.
Время работы алгоритма —
.