Сортировка Пирамидальная-Кучей (Heap-Sort)

Подробности: Категория: Сортировка и поиск

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

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

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

Худшее время	O(n log n)
Лучшее время	O(n log n)
Среднее время	O(n log n)

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

Массив	Описание шага
5 3 4 1 2	Строим кучу из исходного массива
Первый проход
2 3 4 1 5	Меняем местами первый и последний элементы
4 3 2 1 5	Строим кучу из первых четырех элементов
Второй проход
1 3 2 4 5	Меняем местами первый и четвертый элементы
3 1 2 4 5	Строим кучу из первых трех элементов
Третий проход
2 1 3 4 5	Меняем местами первый и третий элементы
2 1 3 4 5	Строим кучу из двух элементов
Четвертый проход
1 2 3 4 5	Меняем местами первый и второй элементы
1 2 3 4 5	Массив отсортирован

Реализация алгоритма на различных языках программирования:

C

#include <stdio.h>
 
#define MAXL 1000
 
void swap (int *a, int *b)
{
  int t = *a;
  *a = *b;
  *b = t;
}
int main()
{
  int a[MAXL], n, i, sh = 0, b = 0;
  scanf ("%i", &n);
  for (i = 0; i < n; ++i)
    scanf ("%i", &a[i]);
  while (1)
  {
    b = 0;
    for (i = 0; i < n; ++i)
    {
      if (i*2 + 2 + sh < n)
      {
        if (a[i+sh] > a[i*2 + 1 + sh] || a[i + sh] > a[i*2 + 2 + sh])
	{
	  if (a[i*2+1+sh] < a[i*2+2+sh])
	  {
	    swap (&a[i+sh], &a[i*2+1+sh]);
	    b = 1;
	  }
	  else if (a[i*2+2+sh] < a[i*2+1+sh])
	  {
	    swap (&a[i+sh],&a[i*2+2+sh]);
	    b = 1;
	  }
	}
      }
      else if (i * 2 + 1 + sh < n)
      {
        if (a[i+sh] > a[i*2+1+sh])
	{
	  swap (&a[i+sh], &a[i*2+1+sh]);
	  b=1;
	}
      }
    }
    if (!b) sh++;
    if (sh+2==n)
      break;
  }
  for (i = 0; i < n; ++i)
    printf ("%i%c", a[i], (i!=n-1)?' ':'\n');
  return 0;
}

C++

#include <iterator>
 
template< typename Iterator >
void adjust_heap( Iterator first
                  , typename std::iterator_traits< Iterator >::difference_type current
                  , typename std::iterator_traits< Iterator >::difference_type size
                  , typename std::iterator_traits< Iterator >::value_type tmp )
{
    typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
 
    diff_t top = current, next = 2 * current + 2;
 
    for ( ; next < size; current = next, next = 2 * next + 2 )
    {
        if ( *(first + next) < *(first + next - 1) )
            --next;
        *(first + current) = *(first + next);
    }
 
    if ( next == size )
        *(first + current) = *(first + size - 1), current = size - 1;
 
    for ( next = (current - 1) / 2;
          top > current && *(first + next) < tmp;
          current = next, next = (current - 1) / 2 )
    {
        *(first + current) = *(first + next);
    }
    *(first + current) = tmp;
}
 
template< typename Iterator >
void pop_heap( Iterator first, Iterator last)
{
    typedef typename std::iterator_traits< Iterator >::value_type value_t;
 
    value_t tmp = *--last;
    *last = *first;
    adjust_heap( first, 0, last - first, tmp );
}
 
template< typename Iterator >
void heap_sort( Iterator first, Iterator last )
{
    typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
    for ( diff_t current = (last - first) / 2 - 1; current >= 0; --current )
        adjust_heap( first, current, last - first, *(first + current) );
 
    while ( first < last )
        pop_heap( first, last-- );
}

C++ (другой вариант)

#include <iostream>
#include <conio.h>
 
using namespace std;
 
void iswap(int &n1, int &n2)
{
    int temp = n1;
    n1 = n2;
    n2 = temp;
}
 
int main()
{
    int const n = 100;
    int a[n];
    for ( int i = 0; i < n; ++i ) { a[i] = n - i; cout << a[i] << " "; }
	//заполняем массив для наглядности.
	//-----------сортировка------------//
	//сортирует по-возрастанию. чтобы настроить по-убыванию,
	//поменяйте знаки сравнения в строчках, помеченных /*(знак)*/
    int sh = 0; //смещение
    bool b = false;
    for(;;)
    {
	b = false;
	for ( int i = 0; i < n; i++ )
	{
	    if( i * 2 + 2 + sh < n )
	    {
		if( ( a[i + sh] > /*<*/ a[i * 2 + 1 + sh] ) || ( a[i + sh] > /*<*/ a[i * 2 + 2 + sh] ) )
		{
		    if ( a[i * 2 + 1 + sh] < /*>*/ a[i * 2 + 2 + sh] )
		    {
			iswap( a[i + sh], a[i * 2 + 1 + sh] );
			b = true;
		    }
		    else if ( a[i * 2 + 2 + sh] < /*>*/ a[ i * 2 + 1 + sh])
		         {
		             iswap( a[ i + sh], a[i * 2 + 2 + sh]);
		             b = true;
		         }
		}
		//дополнительная проверка для последних двух элементов
               //с помощью этой проверки можно отсортировать пирамиду
               //состоящую всего лишь из трех элементов
		    if( a[i*2 + 2 + sh] < /*>*/ a[i*2 + 1 + sh] )
			{
			iswap( a[i*2+1+sh], a[i * 2 +2+ sh] );
                        b = true;
			}
	    }
	    else if( i * 2 + 1 + sh < n )
	         {
	             if( a[i + sh] > /*<*/ a[ i * 2 + 1 + sh] )
	             {
	                 iswap( a[i + sh], a[i * 2 + 1 + sh] );
	                 b = true;
	             }
	         }
	}
	if (!b) sh++; //смещение увеличивается, когда на текущем этапе
		      //сортировать больше нечего
	if ( sh + 2 == n ) break;
    }  //конец сортировки
 
 
    cout << endl << endl;
    for ( int i = 0; i < n; ++i ) cout << a[i] << " ";
 
 
    getch();
    return 0;
}

C#

static Int32 add2pyramid(Int32[] arr, Int32 i, Int32 N)
        {
            Int32 imax;
            Int32 buf;
            if ((2 * i + 2) < N)
            {
                if (arr[2 * i + 1] < arr[2 * i + 2]) imax = 2 * i + 2;
                else imax = 2 * i + 1;
            }
            else imax = 2 * i + 1;
            if (imax >= N) return i;
            if (arr[i] < arr[imax])
            {
                buf = arr[i];
                arr[i] = arr[imax];
                arr[imax] = buf;
                if (imax < N / 2) i = imax;
            }
            return i;
        }
 
        static void Pyramid_Sort(Int32[] arr, Int32 len)
        {
            //step 1: building the pyramid
            for (Int32 i = len / 2 - 1; i >= 0; --i)
            {
                long prev_i = i;
                i = add2pyramid(arr, i, len);
                if (prev_i != i) ++i;
            }
 
            //step 2: sorting
            Int32 buf;
            for (Int32 k = len - 1; k > 0; --k)
            {
                buf = arr[0];
                arr[0] = arr[k];
                arr[k] = buf;
                Int32 i = 0, prev_i = -1;
                while (i != prev_i)
                {
                    prev_i = i;
                    i = add2pyramid(arr, i, k);
                }
            }
        }
 
        static void Main(string[] args)
        {
              Int32[] arr = new Int32[100];
              //заполняем массив случайными числами
              Random rd = new Random();
              for(Int32 i = 0; i < arr.Length; ++i) {
                 arr[i] = rd.Next(1, 101);
              }
              System.Console.WriteLine("The array before sorting:");
              foreach (Int32 x in arr)
              {
                 System.Console.Write(x + " ");
              }
              //сортировка
              Pyramid_Sort(arr, arr.Length);
 
              System.Console.WriteLine("\n\nThe array after sorting:");
              foreach (Int32 x in arr)
              {
                 System.Console.Write(x + " ");
              }
              System.Console.WriteLine("\n\nPress the <Enter> key");
              System.Console.ReadLine();
        }

C# (другой вариант)

public class Heap<T>
{
	private T[] _array; //массив сортируемых элементов
	private int heapsize;//число необработанных элементов
	private IComparer<T> _comparer;
	public Heap(T[] a, IComparer<T> comparer){
		_array = a;
		heapsize = a.Length;
		_comparer = comparer;
	}
 
	public void HeapSort(){
		build_max_heap();//Построение пирамиды
		for(int i = _array.Length - 1; i > 0; i--){
 
			T temp = _array[0];//Переместим текущий максимальный элемент из нулевой позиции в хвост массива
			_array[0] = _array[i];
			_array[i] = temp;
 
			heapsize--;//Уменьшим число необработанных элементов
			max_heapify(0);//Восстановление свойства пирамиды
		}
	}
 
	private int parent (int i) { return (i-1)/2; }//Индекс родительского узла
	private int left (int i) { return 2*i+1; }//Индекс левого потомка
	private int right (int i) { return 2*i+2; }//Индекс правого потомка
 
	//Метод переупорядочивает элементы пирамиды при условии,
        //что элемент с индексом i меньше хотя бы одного из своих потомков, нарушая тем самым свойство невозрастающей пирамиды
	private void max_heapify(int i){
		int l = left(i);
		int r = right(i);
		int lagest = i;
		if (l<heapsize && _comparer.Compare(_array[l], _array[i])>0)
			lagest = l;
		if (r<heapsize && _comparer.Compare(_array[r], _array[lagest])>0)
			lagest = r;
		if (lagest != i)
		{
			T temp = _array[i];
			_array[i] = _array[lagest];
			_array[lagest] = temp;
 
			max_heapify(lagest);
		}
	}
 
	//метод строит невозрастающую пирамиду
	private void build_max_heap(){
		int i = (_array.Length-1)/2;
 
		while(i>=0){
			max_heapify(i);
			i--;
		}
	}
 
}
 
public class IntComparer : IComparer<int>
{
	public int Compare(int x, int y) {return x-y;}
}
 
public static void Main (string[] args)
{
	int[] arr = Console.ReadLine().Split(' ').Select(s=>int.Parse(s)).ToArray();//вводим элементы массива через пробел
	IntComparer myComparer = new IntComparer();//Класс, реализующий сравнение
	Heap<int> heap = new Heap<int>(arr, myComparer);
	heap.HeapSort();
}

Здесь T - любой тип, на множестве элементов которого можно ввести отношение частичного порядка.

Pascal

Вместо «SomeType» следует подставить любой из арифметических типов (например integer).

type  SomeType=integer;
procedure Sort(var Arr: array of SomeType; Count: Integer);
  
  procedure DownHeap(index, Count: integer; Current: SomeType);
  //Функция пробегает по пирамиде восстанавливая ее
  //Также используется для изначального создания пирамиды
  //Использование: Передать номер следующего элемента в index
  //Процедура пробежит по всем потомкам и найдет нужное место для следующего элемента
  var
    Child: Integer;
  begin
    while index < Count div 2 do begin
      Child := (index+1)*2-1;
      if (Child < Count-1) and (Arr[Child] < Arr[Child+1]) then
        Child:=Child+1;
      if Current >= Arr[Child] then
        break;
      Arr[index] := Arr[Child];
      index := Child;
    end;
    Arr[index] := Current;
  end;
  
//Основная функция
var
  i: integer;
  Current: SomeType;
begin
  //Собираем пирамиду
  for i := (Count div 2)-1 downto 0 do
    DownHeap(i, Count, Arr[i]);
  //Пирамида собрана. Теперь сортируем
  for i := Count-1 downto 0 do begin
    Current := Arr[i]; //перемещаем верхушку в начало отсортированного списка
    Arr[i] := Arr[0];
    DownHeap(0, i, Current); //находим нужное место в пирамиде для нового элемента
  end;
end;
var tarr:array of SomeType;
i,n:SomeType;
begin
  writeln('Введите размер массива: ');
  readln(n);
  setlength(tarr,n) ;//Выделяем память под динамический массив
  randomize;
  for i:=0 to n-1 do begin
  tarr[i]:=random(500);//Генерируем случайность
  write (tarr[i]:4);
  end;
  writeln();
  writeln('Всё сортирует');
  Sort(tarr,n);
  for i:=0 to n-1 do begin
  write (tarr[i]:4);
  end;
end.

Pascal (другой вариант)

Примечание: myarray = array[1..Size] of integer; N — количество элементов массива

procedure HeapSort(var m: myarray; N: integer);
var
  i: integer;
 
  procedure Swap(var a,b:integer);
  var
    tmp: integer;
  begin
    tmp:=a;
    a:=b;
    b:=tmp;
  end;
 
  procedure Sort(Ns: integer);
  var
    i, tmp, pos, mid: integer;
  begin
    mid := Ns div 2;
    for i := mid downto 1 do
    begin
      pos := i;
      while pos<=mid do
      begin
        tmp := pos*2;
        if tmp<Ns then
        begin
          if m[tmp+1]<m[tmp] then
            tmp := tmp+1;
          if m[pos]>m[tmp] then
          begin
            Swap(m[pos], m[tmp]);
            pos := tmp;
          end
          else
            pos := Ns;
        end
        else
          if m[pos]>m[tmp] then
          begin
            Swap(m[pos], m[tmp]);
            pos := Ns;
          end
          else
            pos := Ns;
        end;
      end;
    end;
begin
  for i:=N downto 2 do
  begin
    Sort(i);
    Swap(m[1], m[i]);
  end;
end;

Pascal (третий вариант)

type  TArray=array [1..10] of integer;
//процедура для перессылки записей

procedure swap(var x,y:integer);
var temp:integer;
begin
  temp:=x;
  x:=y;
  y:=temp;
end;
  
//процедура приведения массива к пирамидальному виду (to pyramide)
procedure toPyr(var data:TArray; n:integer); //n - размерность массива
var i:integer;
begin
  for i:=n div 2 downto 1 do begin
    if 2*i<=n then if data[i]<data[2*i] then swap(data[i],data[2*i]);
    if 2*i+1<=n then if data[i]<data[2*i+1] then swap(data[i],data[2*i+1]);
  end;
end;
  
//процедура для сдвига массива влево
procedure left(var data:TArray; n:integer);
var i:integer;
    temp:integer;
begin
  temp:=data[1];
  for i:=1 to n-1 do
    data[i]:=data[i+1];
  data[n]:=temp;
end;
  
//основная программа
var a:TArray;
i,n:integer;
begin
  n:=10;//Не больше 10, потому что массив статический - 
        //type  TArray=array [1..10] of integer;
  randomize;
  for i:=1 to n do begin
   a[i]:=random(500);//Генерируем случайность
   write (a[i]:4);
  end;
  for i:=n downto 1 do begin
    topyr(a,i);
    left(a,n);
  end;
  writeln();
  writeln('Сортируем');
  for i:=1 to n do begin
   write (a[i]:4);
   end;
end.

Python

def heapSort(li):
    """Сортирует список в возрастающем порядке с помощью алгоритма пирамидальной сортировки"""
 
    def downHeap(li, k, n):
        new_elem = li[k]
        while 2*k+1 < n:
            child = 2*k+1
            if child+1 < n and li[child] < li[child+1]:
                child += 1
            if new_elem >= li[child]:
                break
            li[k] = li[child]
            k = child
        li[k] = new_elem
 
    size = len(li)
    for i in range(size//2-1,-1,-1):
        downHeap(li, i, size)
    for i in range(size-1,0,-1):
        temp = li[i]
        li[i] = li[0]
        li[0] = temp
        downHeap(li, 0, i)

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 sift(pi, unsorted):
        i_gt = lambda a, b: a if s[a] > s[b] else b
        while pi*2+2 < unsorted:
            gtci = i_gt(pi*2+1, pi*2+2)
            swap(pi, gtci)
            pi = gtci
    # heapify
    for i in range((sl/2)-1, -1, -1):
        sift(i, sl)
    # sort
    for i in range(sl-1, 0, -1):
        swap(i, 0)
        sift(0, i)

Perl

@out=(6,4,2,8,5,3,1,6,8,4,3,2,7,9,1)
$N=@out+0;
if($N>1){
    while($sh+2!=$N){
	$b=undef;
	for my$i(0..$N-1){
	    if($i*2+2+$sh<$N){
		if($out[$i+$sh]gt$out[$i*2+1+$sh] || $out[$i+$sh]gt$out[$i*2+2+$sh]){
	            if($out[$i*2+1+$sh]lt$out[$i*2+2+$sh]){
			($out[$i*2+1+$sh],$out[$i+$sh])=($out[$i+$sh],$out[$i*2+1+$sh]);
			$b=1;
		    }elsif($out[$i*2+2+$sh]lt$out[$i*2+1+$sh]){
			($out[$i*2+2+$sh],$out[$i+$sh])=($out[$i+$sh],$out[$i*2+2+$sh]);
			$b=1;
		    }
		}elsif($out[$i*2+2+$sh]lt$out[$i*2+1+$sh]){
		    ($out[$i*2+1+$sh],$out[$i*2+2+$sh])=($out[$i*2+2+$sh],$out[$i*2+1+$sh]);
		    $b=1;
		}
	    }elsif($i*2+1+$sh<$N && $out[$i+$sh]gt$out[$i*2+1+$sh]){
		($out[$i+$sh],$out[$i*2+1+$sh])=($out[$i*2+1+$sh],$out[$i+$sh]);
		$b=1;
	    }
	}
	++$sh if!$b;
	last if$sh+2==$N;
    }
}

Java

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

Достоинства

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

Недостатки

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

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

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

При написании статьи были использованы открытые источники сети интернет :

Wikipedia

Kvodo

Youtube