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

Подробности

Категория: Сортировка и поиск

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

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

Необходимо отсортировать массив , размером . Построим на базе этого массива за невозрастающую кучу. Так как по свойству кучи максимальный элемент находится в корне, то, поменявшись его местами с , он встанет на свое место. Далее вызовем процедуру , предварительно уменьшив на . Она за просеет на нужное место и сформирует новую кучу (так как мы уменьшили ее размер, то куча располагается с по , а элемент находится на своем месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с , а с . Делая аналогичные действия, пока не станет равен , мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.

Пусть дана последовательность из элементов .

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

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(1) дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки

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

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

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

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

Wikipedia

Kvodo

Youtube