Алгоритмы сортировки. Быстрая сортировка (quicksort). Сортировка с помощью кучи (heapsort). Сортировки за линейное время, страница 2

Сортировка кучей (как и сортировка слиянием, описанная в предыдущем разделе) относится к классу сортировок, время работы которых равно Θ(nlogn). Следует заметить, что к этому классу формально не относится быстрая сортировка, которая вообще не имеет в общем случае асимптотически точной оценки. Кроме того, сортировка кучей не использует Θ(n) дополнительной памяти, как, скажем, сортировка слиянием, что выгодно отличает её от последней (сортировке с помощью кучи для работы достаточно Θ(1) памяти).

2.1  Определение и свойства двоичной кучи

Двоичной кучей (binary heap) называется массив, упорядоченный определённым образом. Двоичную кучу удобнее всего рассматривать как двоичное дерево, которое выложено в один ряд уровень за уровнем, и все уровни которого кроме, быть может, последнего заполнены. Высота такого дерева равна Θ(log n), благодаря чему основные операции с кучей выполняются за время O(log n). Двоичная куча может и не занимать всего массива, в котором находится, поэтому в алгоритмах на куче удобно оперировать размером кучи и размером массива отдельно.

Массив A, содержащий кучу, удобней всего индексировать, начиная с 1. В таком случае индекс предка любой вершины с индексом i (кроме корня – элемента A[1]) равен floor(i / 2), а индексы левого и правого потомков этой вершины равны, соответственно, 2i и 2i + 1. Поэтому для перемещения по куче удобно использовать следующие функции:

//Возвращает индекс предка вершины с индексом i

inline int parent(int i)

{

  return (i - 1) >> 1;

}

//Возвращает индекс левого потомка вершины с индексом i

inline int left(int i)

{

  return i << 1 | 1;

}

//Возвращает индекс правого потомка вершины с индексом i

inline int right(int i)

{

  return (i + 1) << 1;

}

Функции реализованы на языке C++, для которого «родным» является индексирование массивов с 0, поэтому предок и потомки ищутся с поправкой на этот факт.

У двоичной кучи есть одно очень важное свойство, которое отличает её от обычного массива (или дерева) и, собственно, и позволяет организовывать сортировку с помощью кучи.

2.1.1  Основное свойство кучи

Все элементы двоичной кучи должны обладать основным свойством кучи – любой элемент кучи всегда больше своих потомков или равен им. То есть, A[i] >= A[left(i)] && A[i] >= A[right(i)] == true для всех вершин, имеющих потомков (здесь i – индекс вершины). Поэтому самый большой элемент кучи всегда является её первым элементом (A[1]).

2.2  Сохранение основного свойства кучи

Для сохранения основного свойства кучи используется простой алгоритм. Сначала смотрится, выполняется ли для выбранной вершины  основное свойство. Если оно не выполняется, то вершина просто-напросто меняется местами с наибольшим из своих потомков и алгоритм выполняется повторно уже для того потомка, с которым произошёл обмен. Этот алгоритм работает только в случае, если для каждого из поддеревьев, корнями которых являются потомки рассматриваемой вершины, основное свойство кучи уже выполняется.

Понятно, что такой алгоритм отрабатывает за время O(log n), поскольку происходит максимум logn рекурсивных вызовов (по высоте дерева). Ниже приведена его реализация на C++.

//Функция восстанавливает основное свойство для вершины с индексом i

//кучи размера heapSize, хранящейся в массиве A

void heapify(int* A, int heapSize, int i)

{

  //Найдём индексы потомков вершины

  int l = left(i);

  int r = right(i);

  //Обнаружим индекс наибольшей из 3-х вершин:

  //исследуемой и левого и правого потомков

  int max = l < heapSize && A[l] > A[i] ? l : i;

  if (r < heapSize && A[r] > A[max]) max = r;

  //Если текущая вершина не является наибольшей, произведём

  //обмен и рекурсивный вызов для новой позиции текущей вершины

  if (max != i) {

    swap(A + i, a + max); //см. быструю сортировку

    heapify(A, heapSize, max);

  }

}