Двоичная куча

Эта статья находится в разработке!

Определение:

Двоичная куча или пирамида — такое двоичное дерево, для которого выполнены три условия: Значение (ключ) в любой вершине не больше, чем значения её потомков. Каждый лист имеет глубину (расстояние до корня) либо [math]d[/math] либо [math]d-1[/math]. Иными словами, если назвать слоем совокупность вершин, находящихся на определённой глубине, то все слои, кроме, быть может, последнего, заполнены полностью. Последний слой заполняется слева направо.

Удобная структура данных для сортирующего дерева — массив [math]A[/math], у которого первый элемент, [math]A[1][/math] — элемент в корне, а потомками элемента [math]A[i][/math] являются [math]A[2i][/math] и [math]A[2i+1][/math]. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть [math]O(logN)[/math], где [math]N[/math] — количество узлов дерева.

Базовые процедуры

Восстановление свойств кучи

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры Shift_Down(просеивание вниз) и Shift_Up(просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией Shift_Down(i). Работа процедуры : если [math]i[/math]-й элемент больше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами [math]i[/math]-й элемент с наибольшим из его сыновей, после чего выполняем Shift_Down для этого сына. Процедура выполняется за время [math]O(logN)[/math].

Shift_Down(i)

 left = 2 * i // левый сын
 right = 2 * i + 1 // правый сын
 // heap_size - количество элементов в куче
 If (left ≤ A.heap_size) and (A[left] < A[i])  
   min = left
 else
   min = i
 If (right ≤ A.heap_size) and (A[right] < A[i])  
   min = right
 else
   min = i
 If (min <> i) 
   Поменять A[i] и A[largest]
   Shift_Down(A, min)

Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функциейShift_Up(i).

Работа процедуры : если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем Shift_Up для этого отца. Иными словами, слишком большой элемент всплывает наверх. Процедура выполняется за время [math]O(logN)[/math].

Shift_Up(i)

 If (A[i] < A[i / 2])
   Поменять A[i] и A[i / 2]
   Shift_Up(i / 2)

Извлечение минимального элемента

Выполняет извлечение минимального элемента из кучи за время [math]O(logN)[/math]. Извлечение выполняется в четыре этапа:

1. Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
2. Последний элемент копируется в корень, после чего удаляется из кучи.
3. Вызывается Shift_Down для корня.
4. Сохранённый элемент возвращается.

extract_min()

 min = A[1]
 A[1] = A[A.heap_size]
 A.heap_size = A.heap_size - 1
 Shift_Down(1)
 return min

Добавление нового элемента

Выполняет добавление элемента в кучу за время [math]O(logN)[/math]. Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью

Insert(key)

 A.heap_size = A.heap_size + 1
 A[A.heap_size] = key;
 Shift_Up(A.heap_size)

Источники

• Двоичная куча