Сортировка кучей — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
  
 
== Реализация ==
 
== Реализация ==
   // Входной массив x, содержащий n элементов.
+
<pre>
   for i = 0 to n - 1
+
heapsort(A)
    min = i;
+
  build_heap(A);
        for j = i + 1 to n - 1
+
   heap_size = A.size;
          if x[j] < x[min]
+
   for i:= 0 to n - 2
              min = j;
+
    swap(A[0], A[n - 1 - i]);
    swap(x[i], x[min]);
+
    heap_size--;
  // Массив x отсортирован
+
    sift_down(0, heap_size);
 
+
</pre>
 
== Пример ==
 
== Пример ==
  

Версия 07:41, 3 июня 2012

Сортировка кучей, пирамидальная сортировка (англ. Heapsort) — алгоритм сортировки, использующий структуру данных двоичная куча. Это нестабильный алгоритм сортировки с гарантированным временем работы [math]\Theta(n\log{n})[/math] , где [math]n[/math] — количество элементов для сортировки, и использующий [math]O(1)[/math] дополнительной памяти.

Алгоритм

Необходимо отсортировать массив [math]A[/math], размером [math]n[/math]. Построим на базе этого массива за [math]O(n)[/math] невозрастающую кучу. Так как по свойству кучи максимальный элемент находится в корне, то, поменявшись его местами с [math]A[n - 1][/math], он встанет на свое место. Далее вызовем процедуру sift_down(0), предварительно уменьшив [math]heap\_size[/math] на [math]1[/math]. Она за [math]O(\log{n})[/math] просеет [math]A[0][/math] на нужное место и сформирует новую кучу (так как мы уменьшили ее размер, то куча располагается с [math]A[0][/math] по [math]A[n - 2][/math], а элемент [math]A[n-1][/math] находится на своем месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с [math]A[n - 1][/math], а с [math]A[n-2][/math]. Проделав аналогичные операции [math]n - 1[/math], мы получим отсортированный массив.

Реализация

heapsort(A)
  build_heap(A);
  heap_size = A.size;
  for i:= 0 to n - 2
    swap(A[0], A[n - 1 - i]);
    heap_size--;
    sift_down(0, heap_size);

Пример

Пусть дана последовательность из [math]5[/math] элементов [math]5, 4, 1, 2, 3[/math].

Массив Описание шага
Первый проход (текущий массив начинается с первого элемента)
5 4 1 2 3 Находим первый минимальный элемент — 1
1 4 5 2 3 Меняем минимальный и первый элементы местами
Второй проход (текущий массив начинается со следующего элемента)
1 5 4 2 3 Находим следующий минимальный элемент — 2
1 2 4 5 3 Меняем минимальный и второй элементы местами
Третий проход (текущий массив начинается со следующего элемента)
1 2 4 5 3 Находим следующий минимальный элемент — 3
1 2 3 5 4 Меняем минимальный и третий элементы местами
Четвертый проход (текущий массив начинается со следующего элемента)
1 2 3 5 4 Находим следующий минимальный элемент — 4
1 2 3 4 5 Меняем минимальный и четвертый элементы местами
1 2 3 4 5 Массив отсортирован


Ссылки

Литература

  • Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4