Двоичная куча (Binary Heap) и сортировка с её помощью.

Строение двоичной кучи и основные операции с ней.

Оглавление

• Алгоритмы и структуры данных.
  • Теория.
    • Определения.
    • Разделяй и властвуй.
    • Методы оценки времени работы рекуррентных соотношений.
    • Доказательство основной теоремы о рекуррентных оценках.
    • Двоичная куча и сортировка с её помощью.
  • Практика.
    • Сравнение времени работы различных алгоритмов сортировки.

По мере реализации пункты оглавления будут заменяться на ссылки.

Двоичной кучей называется массив, обладающий определённым свойством упорядоченности. Рассмотрим двоичное дерево i-ая вершина которого соответствует i-му элементу массива, а его родительская вершина соответствует i/2-му элементу массива, причём $$A[Parent(i)] \geqslant A[i].$$ Последнее условие называют основным свойством кучи (heap property).

Операции над двоичной кучей

Сводная таблица рассматриваемых операций

Heapify

Процедура Heapify позволяет поддерживать основное свойство кучи. На вход данной процедуре подаётся массив A и индекс i, причём полагается, что для деревьев с корнями Left(i), Right(i) основное свойство кучи уже выполнено. Целью данной процедуры является перестановка элемента i с элементами одного из его поддеревьев до тех пор, пока для этого поддерева вновь не будет выполнено основное свойство кучи.

Heapify(A,i, heapSize=len(A))
    l = Left(i)
    r = Right(i)
    
    if l <= heapSize and A[l] > A[i]:
        then largest = l
        else largest = i
    
    if r <= heapSize and A[r] > A[largest]:
        then largest = r
    
    if largest != i:
       then swap(A[i], A[largest])
            Heapify(A, largest)

Процедура Heapify находит максимальный из элементов A[i], A[Left(i)], A[Right(i)], затем меняет его местами с A[i]. Если элемент A[i] максимальный, то основное свойство выполнено и можно прекратить работу алгоритма, иначе мы рекурсивно вызываем Heapify для элемента A[largest], так как предыдущая замена могла нарушить основное свойство кучи в поддереве с корнем соответствующим A[largest].

На каждом этапе работы процедуры Heapify, не считая рекурсии, затрачиваемое время составляет $$\Theta(1).$$ Пусть для дерева, содержащего $$n$$ элементов время работы процедуры Heapify равняется $$T(n),$$ тогда если дерево с корнем в i состоит из $$n$$ элементов, то, так как поддеревья $$A[Left(i)],; A[Right(i)]$$ содержат не более $$2n/3$$ элементов, общее время работы процедуры подчиняется следующей оценке:

$$ T(n) \leqslant T(2n/3) + \Theta(1). $$

Последнее, в силу теоремы о рекуррентных оценках, означает, что $$T(n)=O(\log{n}).$$ Интуитивное объяснение такой оценки заключается в том, что за каждый шаг мы спускаемся по дереву высотой $$\log{n}$$ вглубь на один уровень, следовательно время работы всей процедуры не может превышать $$O(\log{n}).$$

BuildHeap

Для превращения массива A в двоичную кучу воспользуемся процедурой Heapify, а именно применим её ко всем вершинам, начиная с нижних. Вершины с индексами большими $$n/2$$ являются листьями, следовательно для них уже выполнено основное свойство кучи. Оставшиеся вершины будут обработаны при помощи процедуры Heapify, причём порядок обхода гарантирует, что для поддеревьев уже выполнено основное свойство кучи.

BuildHeap(A)
    length = len(A)
    
    for i=length/2, i>0, i--:
        Heapify(A,i)

Очевидно, что время работы процедуры BuildHeap не может превышать $$O(n\log{n})$$, так как число вызовов Heapify равняется $$O(n),$$ а её время работы $$O(\log{n}).$$ Эту оценку можно уточнить. Время работы процедуры Heapify пропорционально высоте вершины, для которой она вызывается. Число вершин высоты $$h$$ не превышает $$n/(2^{h+1}),$$ следовательно время работы BuildHeap не превосходит

$$ \sum_{h=0}^{[\log{n}]}\frac{n}{2^{h+1}}O(h) = O(n \sum_{h=0}^{[\log{n}]}\frac{n}{2^{h+1}}) \leqslant O(n\sum_{h=0}^{\infty}\frac{n}{2^{h+1}})=\Big|\sum_{h=0}^{\infty}\frac{n}{2^{h+1}}=2\Big|=O(n). $$

Рассмотрим пример работы процедуры на следующем массиве, красным помечены вершины, в которых нарушается основное правило кучи:

Вызовем на ней процедуру BuildHeap.

Таким образом исходный массив принял вид

HeapSort

Сортировка массива при помощи кучи состоит из двух частей: построения двоичной кучи и последующей её обработки. После построения кучи максимальный элемент находится находится в корне двоичного дерева A[1]. Этот элемент меняется местами с A[n], уменьшить размер кучи на 1 и восстановить основное свойство в корневой вершине.

HeapSort(A)
    BuildHeap(A)
    
    heapSize=len(A)
    for i=len(A), i>1, i++:
        swap(A[1], A[i])
        heapSize = heapSize - 1
        Heapify(A,1,heapSize)

Время работы процедуры HeapSort составляет $$O(n\log{n}),$$ так как BuildHeap занимает $$O(n),$$ а каждый из n-1 вызовов Heapify занимает $$O(\log{n}).$$

Продемонстрируем работу второй части процедуры HeapSort на примере из BuildHeap

Принцип работы ExtractMax и Insert будет описан в заметке об очередях с приоритетами (Priority Queue).

Литература

1. Т. Кормен. Алгоритмы. Построение и анализ. – М.: МЦНМО, 2001. — 138-146 c.