Пирамидальная сортировка

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Анимированная схема алгоритма

Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»[1]) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов.[2] Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).

Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.

История создания[править | править вики-текст]

Пи­ра­ми­даль­ная сор­ти­ров­ка бы­ла пред­ло­же­на Дж. Уи­льям­сом в 1964 го­ду.[1]

Алгоритм[править | править вики-текст]

Пример сортирующего дерева
структура хранения данных сортирующего дерева

Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия:

  1. Каждый лист имеет глубину либо d, либо d-1, d — максимальная глубина дерева.
  2. Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.

Удобная структура данных для сортирующего дерева — такой массив Array, что Array[1] — элемент в корне, а потомки элемента Array[i] являются Array[2i] и Array[2i+1].

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дерева:

\text{Array}[i]\geq \text{Array}[2i]

\text{Array}[i]\geq \text{Array}[2i+1]

при 1\leq i<n/2.

Этот шаг требует O(n) операций.

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], … , Array[n-1] в сортирующее дерево. Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], … , Array[n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[1], Array[2], … , Array[n] — упорядоченная последовательность.

Этот шаг требует O(n \log n) операций.

Достоинства и недостатки[править | править вики-текст]

Достоинства

  • Имеет доказанную оценку худшего случая O(n\cdot\log n).
  • Сортирует на месте, то есть требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки

  • Сложен в реализации.
  • Неустойчив — для обеспечения устойчивости нужно расширять ключ.
  • На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
  • На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.
  • Методу требуется «мгновенный» прямой доступ; не работает на связанных списках и других структурах памяти последовательного доступа.

Сортировка слиянием при расходе памяти O(n) быстрее (O(n\cdot\log n) с меньшей константой) и не подвержена деградации на неудачных данных.

Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.

Пример[править | править вики-текст]

Python:

def heapsort(s):                               
    sl = len(s)                                    
 
    def swap(pi, ci):                              
        if s[pi] < s[ci]:                          
            s[pi], s[ci] = s[ci], s[pi]            
 
    def shift(pi, unsorted):                        
        i_gt = lambda a, b: a if s[a] > s[b] else b
        while pi*2+1 < unsorted:                   
            gtci = i_gt(pi*2+1, pi*2+2) if pi*2+2 < unsorted else pi*2+1            
            swap(pi, gtci)                         
            pi = gtci                              
    # heapify                                      
    for i in range((sl/2)-1, -1, -1):              
        shift(i, sl)                                
    # sort                                         
    for i in range(sl-1, 0, -1):                   
        swap(i, 0)                                 
        shift(0, i)

C#:

static void HeapSort(int[] a)
{
    int i;
    int temp;
 
    for (i = a.Length / 2 - 1; i >= 0; i--)
    {
        shiftDown(a, i, a.Length);
    }
 
    for (i = a.Length - 1; i >= 1; i--)
    {
        temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        shiftDown(a, 0, i);
    }
}
 
static void shiftDown(int[] a, int i, int j)
{
    bool done = false;
    int maxChild;
    int temp;
 
    while ((i * 2 + 1 < j) && (!done))
    {
        if (i * 2 + 1 == j - 1)
            maxChild = i * 2 + 1; 
        else if (a[i * 2 + 1] > a[i * 2 + 2])
            maxChild = i * 2 + 1;
        else
            maxChild = i * 2 + 2;
 
        if (a[i] < a[maxChild])
        {
            temp = a[i];
            a[i] = a[maxChild];
            a[maxChild] = temp;
            i = maxChild;
        }
        else
        {
            done = true;
        }
    }
}

D:

void HeapSort(uint[] a)
 {
  int i;
  int temp;
  int len = a.length;
  for (i = len/ 2 - 1; i >= 0; i--)
   {
    ShiftDown(a, i, len);
   }
  for (i = len - 1; i > 0; i--)
   {
    temp = a[0];
    a[0] = a[i];
    a[i] = temp;
    ShiftDown(a, 0, i);
   }
 }
 
void ShiftDown(uint[] a, int i, int j)
 {
  uint temp;
  uint left = 2 * i + 1;
  uint right = left + 1;
  uint MaxChild = left;
  while (MaxChild < j)
   {
    if (right < j)
     {
      if (a[left] < a[right])
       {
        MaxChild = right;
       }
     }
    if (a[i] < a[MaxChild])
     {
      temp = a[i];
      a[i] = a[MaxChild];
      a[MaxChild] = temp;
     }
    else
     {
      break;
     }
    i = MaxChild;
    left = 2 * i + 1;
    right = left + 1;
    MaxChild = left;
   }
 }

Delphi(Pascal):

Procedure HeadSort(var a: array of Integer);
var
  i,temp,len: Integer;
  procedure ShiftDown(var a: array of Integer; i,j: integer);
  var
    Left,Right,MaxChild,temp: Integer; 
  begin
    left:=2*i+1;
    right:=left+1;
    MaxChild:=left;
    while MaxChild < j do 
    begin
      if Right < j then
      begin
        if a[left] < a[right] then MaxChild:=right;
        if a[i]<a[MaxChild] then 
        begin
          temp:=a[i];
          a[i]:=a[MaxChild];
          a[MaxChild]:=temp;
        end;
      end
      else break;
      i:=MaxChild;
      left:=2*i+1;
      right:=left+1;
      MaxChild:=left;
    end;
  end;
begin
  len:=Length(a);
  for i:=Round(len/2)-1 Downto 0 do 
    ShiftDown(a,i,len);
 
  for i:=len-1 DownTo 1 Do 
  begin
    temp:=a[0];
    a[0]:=a[i];
    a[i]:=temp;
    ShiftDown(a,0,i);
  end;
end;

Java:

/**
 * Класс для сортировки массива целых чисел с помощью кучи.
 * Методы в классе написаны в порядке их использования. Для сортировки 
 * вызывается статический метод sort(int[] a)
 *
 */
class HeapSort {
	/**
	 * Сортировка с помощью кучи.
	 * Сначала формируется куча:
	 * @see HeapSort#buildHeap(int[])
	 * Теперь максимальный элемент массива находится в корне кучи. Его нужно 
	 * поменять местами с последним элементом и убрать из кучи (уменьшить 
	 * размер кучи на 1). Теперь в корне кучи находится элемент, который раньше
	 * был последним в массиве. Нужно переупорядочить кучу так, чтобы 
	 * выполнялось основное условие кучи - a[parent]>=a[child]:
	 * @see #heapify(int[], int, int)
	 * После этого в корне окажется максимальный из оставшихся элементов.
	 * Повторить до тех пор, пока в куче не останется 1 элемент
	 * 
	 * @param a сортируемый массив
	 */
	public static void sort(int[] a) {
		buildHeap(a);
		int length = a.length - 1;
		while (length > 0) {
			swap(a, 0, length);
			heapify(a, length, 0);
			length--;
		}
	}
 
	/**
	 * Построение кучи. Поскольку элементы с номерами начиная с a.length / 2 + 1
	 * это листья, то нужно переупорядочить поддеревья с корнями в индексах
	 * от 0 до a.length / 2 (метод heapify вызывать в порядке убывания индексов)
	 * 
	 * @param a - массив, из которого формируется куча
	 */
	private static void buildHeap(int[] a) {
		for (int i = a.length / 2; i >= 0; i--) {
			heapify(a, a.length, i);
		}
	}
 
	/**
	 * Переупорядочивает поддерево кучи начиная с узла i так, чтобы выполнялось 
	 * основное свойство кучи - a[parent] >= a[child].
	 * 
	 * @param a - массив, из которого сформирована куча
	 * @param length - размер поддерева
	 * @param i - корень поддерева, для которого происходит переупорядочивание
	 */
	private static void heapify(int[] a, int length, int i) {
		int l = left(i);
		int r = right(i);
		int largest = i;
		if (l < length && a[i] < a[l]) {
			largest = l;
		} 
		if (r < length && a[largest] < a[r]) {
			largest = r;
		}
		if (i != largest) {
			swap(a, i, largest);
			heapify(a, length, largest);
		}
	}
 
	/**
	 * Возвращает индекс правого потомка текущего узла
	 * 
	 * @param i индекс текущего узла кучи
	 * @return индекс правого потомка
	 */
	private static int right(int i) {
		return 2 * i + 1;
	}
 
	/**
	 * Возвращает индекс левого потомка текущего узла
	 * 
	 * @param i индекс текущего узла кучи
	 * @return индекс левого потомка
	 */
	private static int left(int i) {
		return 2 * i + 2;
	}
 
	/**
	 * Меняет местами два элемента в массиве
	 * 
	 * @param a массив
	 * @param i индекс первого элемента
	 * @param j индекс второго элемента
	 */
	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
 
}

Применение[править | править вики-текст]

Алгоритм "сортировка кучей" активно применяется в ядре Linux.

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • Ананий В. Левитин Глава 6. Метод преобразования: Пирамиды и пирамидальная сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 275-284. — ISBN 5-8459-0987-2.
  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 182-188. — ISBN 5-8459-0857-4.

Ссылки[править | править вики-текст]