Двоичная куча — различия между версиями
Ильнар (обсуждение | вклад) |
Ильнар (обсуждение | вклад) |
||
Строка 83: | Строка 83: | ||
</code> | </code> | ||
− | ==Построение кучи за O(n) == | + | ===Построение кучи за O(n) === |
{{Определение | definition = | {{Определение | definition = | ||
'''<tex>D</tex>-куча''' {{---}} это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно <tex>d</tex> потомков. | '''<tex>D</tex>-куча''' {{---}} это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно <tex>d</tex> потомков. | ||
Строка 118: | Строка 118: | ||
}} | }} | ||
− | ==Слияние двух куч== | + | <code style="display:inline-block"> |
− | Даны две кучи <tex>a</tex> и <tex>b</tex>, требуется объединить эти две кучи. | + | '''function''' heapify(): |
− | + | '''for''' i = a.heapSize / 2 '''downto''' 0 | |
− | Добавим все элементы кучи <tex>b</tex> в конец массива <tex>a</tex>, после чего вызовем функцию построения кучи. Процедура выполняется за время <tex>O( | + | siftDown(i) |
+ | </code> | ||
+ | ===Слияние двух куч=== | ||
+ | Даны две кучи <tex>a</tex> и <tex>b</tex>, размерами <tex>n</tex> и <tex>m</tex>, требуется объединить эти две кучи. | ||
+ | ====Наивная реализация==== | ||
+ | Поочередно добавим все элементы из <tex>b</tex> в <tex>a</tex>. Время работы {{---}} <tex>O(m \log(n+m))</tex>. | ||
+ | <code style="display:inline-block"> | ||
+ | '''function''' merge(a, b : '''Heap'''): | ||
+ | '''while''' b.heapSize <tex>\neq</tex> 0 | ||
+ | a.insert(b.extractMin()) | ||
+ | </code> | ||
+ | ====Реализация с помощью построения кучи==== | ||
+ | Добавим все элементы кучи <tex>b</tex> в конец массива <tex>a</tex>, после чего вызовем функцию построения кучи. Процедура выполняется за время <tex>O(n + m)</tex>. | ||
<code style="display:inline-block"> | <code style="display:inline-block"> | ||
− | '''function''' merge(a, b : ''' | + | '''function''' merge(a, b : '''Heap'''): |
'''for''' i = 0 '''to''' b.heapSize - 1 | '''for''' i = 0 '''to''' b.heapSize - 1 | ||
a.heapSize = a.heapSize + 1 | a.heapSize = a.heapSize + 1 | ||
Строка 131: | Строка 143: | ||
</code> | </code> | ||
− | ==Поиск k-ого элемента== | + | ===Поиск k-ого элемента=== |
Требуется найти <tex>k</tex>-ый по величине элемент в куче. | Требуется найти <tex>k</tex>-ый по величине элемент в куче. | ||
− | # Создаем новую кучу, в которой будем хранить пару <tex>\langle value, index \rangle</tex>, где <tex>value</tex> {{---}} значение элемента, а <tex>index</tex> {{---}} индекс элемента в основном массиве, и добавляем в нее корень кучи. | + | # Создаем новую кучу, в которой будем хранить пару <tex>\langle \mathtt{value}, \mathtt{index} \rangle</tex>, где <tex>\mathtt{value}</tex> {{---}} значение элемента, а <tex>\mathtt{index}</tex> {{---}} индекс элемента в основном массиве, и добавляем в нее корень кучи. |
# Возьмем корень новой кучи и добавим её детей из основной кучи, после чего удалим корень. Проделаем этот шаг <tex>k - 1</tex> раз. | # Возьмем корень новой кучи и добавим её детей из основной кучи, после чего удалим корень. Проделаем этот шаг <tex>k - 1</tex> раз. | ||
# В корне новой кучи будет находиться ответ. | # В корне новой кучи будет находиться ответ. | ||
Строка 153: | Строка 165: | ||
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Приоритетные очереди]] | [[Категория: Приоритетные очереди]] | ||
+ | [[Категория: Структуры данных]] |
Версия 23:09, 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] heapify(a)
Поиск k-ого элемента
Требуется найти
-ый по величине элемент в куче.- Создаем новую кучу, в которой будем хранить пару , где — значение элемента, а — индекс элемента в основном массиве, и добавляем в нее корень кучи.
- Возьмем корень новой кучи и добавим её детей из основной кучи, после чего удалим корень. Проделаем этот шаг раз.
- В корне новой кучи будет находиться ответ.