Перейти к содержанию

Реализации алгоритмов/Сортировка/Пирамидальная

Материал из Викиучебника — открытых книг для открытого мира
Логотип Википедии
Логотип Википедии

В Википедии имеется статья по теме «Пирамидальная сортировка»

C

[править]
#include <stdio.h>

#define MAXL 1000

#define  root i+sh
#define  left 2*i+1+sh
#define right 2*i+2+sh

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 (right < n)
      {
        if (a[root] > a[left] || a[root] > a[right])
	      {
	        if (a[left] < a[right])
	        {
	          swap (&a[root], &a[left]);
	          b = 1;
	        }
	        else if (a[right] < a[left])
	        {
	          swap (&a[root], &a[right]);
	          b = 1;
	        }
	      }
      }
      else if (left < n)
      {
        if (a[root] > a[left])
	      {
	        swap (&a[root], &a[left]);
	        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++

[править]

Вариант № 1

[править]
#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-- );
}

Вариант № 2

[править]
#include <iostream>


void iswap (int &n1, int &n2) 
{
    int temp = n1;
    n1 = n2;
    n2 = temp;
}

int main () 
{
    const int n = 100;
    int a[n];

    // Для наглядности заполняем массив числами от n до 0.
    for (int i = 0; i < n; i++) {
        a[i] = n - i;
        std::cout << a[i] << ' ';
    }

	// ----------- Сортировка ------------
	// Сортирует по возрастанию. Чтобы получить сортировку по убыванию,
	// поменяйте знаки сравнения в строчках, помеченных /*(знак)*/
    int sh = 0; // Смещение
    bool b;
    do 
    {
	    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; // Смещение увеличивается, когда на текущем этапе сортировать больше нечего
    } while (sh + 2 < n); // Конец сортировки

    std::cout << std::endl << std::endl;
    for (int i = 0; i < n; i++)
        std::cout << a[i] << ' ';

    return 0;
}

C#

[править]

Вариант № 1

[править]
       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();
        }

Вариант № 2

[править]
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 - любой тип, на множестве элементов которого можно ввести отношение частичного порядка.

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 + 2;
	}
	
	/**
	 * Возвращает индекс левого потомка текущего узла
	 * 
	 * @param i индекс текущего узла кучи
	 * @return индекс левого потомка
	 */
	private static int left(int i) {
		return 2 * i + 1;
	}
	
	/**
	 * Меняет местами два элемента в массиве
	 * 
	 * @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;
	}
	
}

Pascal

[править]

Вариант № 1

[править]

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

procedure HeapSort (var sequence: array of T; count: Word);

    procedure SiftDown (index, count: Word; current: T);
    {
        Функция пробегает по пирамиде восстанавливая ее
        Также используется для изначального создания пирамиды
        Использование: Передать номер следующего элемента в index
        Процедура пробежит по всем потомкам и найдет нужное место для следующего элемента
    }
    var child: Word;
    begin
        while index < count div 2 do
        begin
            child := (index + 1) * 2 - 1;
            if (child < count - 1) and (sequence[child] < sequence[child + 1]) then
                child := child + 1;
            if current >= sequence[child] then
                break;
            sequence[index] := sequence[child];
            index := child
        end;
        sequence[index] := current
    end;

{ Основная функция }
var i: Integer;
    current: T;
begin
    { Собираем пирамиду }
    for i := (count div 2) - 1 downTo 0 do
        SiftDown(i, count, sequence[i]);
    { Пирамида собрана. Теперь сортируем }
    for i := count - 1 downTo 0 do
    begin
        current := sequence[i]; { перемещаем верхушку в начало отсортированного списка }
        sequence[i] := sequence[0];
        SiftDown(0, i, current) { находим нужное место в пирамиде для нового элемента }
    end
end;

Здесь нет вывода и ввода массива. Либо случайный, либо пользователем.

Вариант № 2

[править]

Примечание: N — количество элементов массива 

procedure HeapSort (var sequence: array of T; N: Integer);
var i: Integer;
    { Выполняет обмен значениями двух элементов массива sequence с указанными индексами }
    procedure SwapItems (index_1, index_2: Word);
    var temp: T;
    begin
        temp := sequence[index_1];
        sequence[index_1] := sequence[index_2];
        sequence[index_2] := temp
    end;

    procedure Sort (Ns: integer);
    var i, child, pos, mid: Integer;
    begin
        mid := Ns div 2;
        for i := mid downTo 1 do
        begin
            pos := i;
            while pos <= mid do
            begin
                child := pos * 2;
                if child < Ns then
                begin
                    if sequence[child + 1] < sequence[child] then
                        child := child + 1;
                    if sequence[child] < sequence[pos] then
                    begin
                        SwapItems(pos, child);
                        pos := child
                    end
                    else
                        pos := Ns
                end
                else if sequence[child] < sequence[pos] then
                begin
                    SwapItems(pos, child);
                    pos := Ns
                end
                else
                    pos := Ns
            end
        end
    end;
begin
    for i := N downTo 2 do
    begin
        Sort(i);
        SwapItems(1, i)
    end
end;

Вариант № 3

[править]
{ Процедура для обмена значений переменных }
procedure swap (var x, y: integer);
var temp: integer;
begin
    temp := x;
    x := y;
    y := temp
end;

{ Процедура приведения массива к пирамидальному виду (to heap) }
procedure ToHeap (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 ShiftLeft (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;

{ Основная программа }
BEGIN
    for i := n downTo 1 do
    begin
        ToHeap(a, i);
        ShiftLeft(a, n);
    end
END.

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;
    }
}

Python

[править]

Приведённые алгоритмы упорядочивают принимаемую последовательность sequence (список, символьную строку) по неубыванию (sequence[i] ≤ sequence[i + 1]). Для упорядочения по невозрастанию (sequence[i] ≥ sequence[i + 1]) необходимо заменить все знаки < на > в строках, помеченных # !

Для большей эффективности вычислений умножение и деление нацело на 2 производятся операторами побитового сдвига влево (<<) и вправо (>>) соответственно. Например parent << 1 вместо parent * 2, length >> 1 вместо length // 2 и т. п.

Проверить работу любой из функций можно добавив, например, следующий код (Python 3; для Python 2 следует опустить скобки в операторах print): 

count = 30 # Количество значений в последовательности
# Заполняем последовательность значениями, расположенными в порядке, обратном желаемому:
sequence = list(range(count, 0, -1))
# Для упорядочения по невозрастанию закомментируйте предыдущую строку и раскомментируйте следующую
# sequence = list(range(1, count))
print("Исходная последовательность:")
print(sequence)
heap_sort(sequence)
print("Упорядоченная последовательность:")
print(sequence)

Вариант № 1

[править]
def heap_sort (sequence):

    def sift_down (parent, limit):
        item = sequence[parent]
        while True:
            child = (parent << 1) + 1
            if child >= limit:
                break
            if child + 1 < limit and sequence[child] < sequence[child + 1]: # !
                child += 1
            if item < sequence[child]:                                      # !
                sequence[parent] = sequence[child]
                parent = child
            else:
                break
        sequence[parent] = item
    # Тело функции heap_sort
    length = len(sequence)
    # Формирование первичной пирамиды
    for index in range((length >> 1) - 1, -1, -1):
        sift_down(index, length)
    # Окончательное упорядочение
    for index in range(length - 1, 0, -1):
        sequence[0], sequence[index] = sequence[index], sequence[0]
        sift_down(0, index)

Вариант № 2

[править]
def heap_sort (sequence):

    def swap_items (index1, index2):
        if sequence[index1] < sequence[index2]:                                 # !
            sequence[index1], sequence[index2] = sequence[index2], sequence[index1]

    def sift_down (parent, limit):
        while True:
            child = (parent + 1) << 1 # То же, что и parent * 2 + 2
            if child < limit:
                if (sequence[child] < sequence[child - 1]):
                    swap_items(parent, child-1)
                    parent = child-1
                else:
                    swap_items(parent, child)
                    parent = child
            else:
                if (child-1<limit):                
                    swap_items(parent,child-1)
                break
    # Тело функции heap_sort
    length = len(sequence)
    # Формирование первичной пирамиды
    for index in range((length >> 1) - 1, -1, -1):
        sift_down(index, length)
    # Окончательное упорядочение
    for index in range(length - 1, 0, -1):
        swap_items(index, 0)
        sift_down(0, index)

Rust

[править]

Приведённые алгоритмы упорядочивают принимаемую последовательность sequence (в её качестве могут выступать массив (array), вектор (Vec), срез (slice)) по неубыванию (sequence[i] ≤ sequence[i + 1]). Для упорядочения по невозрастанию (sequence[i] ≥ sequence[i + 1]) необходимо закомментировать знаки < и раскомментировать > в местах, помеченных /*>*/

Для большей эффективности вычислений умножение и деление нацело на 2 производятся операторами побитового сдвига влево (<<) и вправо (>>) соответственно. Например parent << 1 вместо parent * 2, length >> 1 вместо length / 2 и т. п.

Проверить работу любой из функций можно добавив, например, следующий код (следует учитывать, что в Rust массивы до 32 элементов могут выводиться макросами print! и println!; для более длинных придётся писать собственную функцию вывода): 

fn main () {
    let mut sequence = [0i32; 30]; // Массив из 30 элементов
    let mut value = sequence.len() as i32;
    // Заполнение последовательности убывающими значениями
    for i in 0..sequence.len() {
        sequence[i] = value;
        value -= 1;
        // Для заполнения возрастающими значениями закомментируйте две предыдущие строки и раскомментируйте следующую:
        // sequence[i] = i as i32 + 1;
    }
    // Вывод исходной последовательности
    println!("Исходная последовательность:\n{:?}", sequence);
    // Упорядочение последовательности
    heap_sort(&mut sequence);
    // Вывод упорядоченной последовательности
    println!("Упорядоченная последовательность:\n{:?}", sequence);
}

Вариант № 1

[править]
fn heap_sort <T: PartialOrd> (sequence: &mut[T]) {
    let length = sequence.len();
    let mut offset = 0usize;
    let mut flag = false;
    while {
        for index in 0..length {
            let left = (index << 1) + 1 + offset;   // Индекс левого ребёнка
            let right = left + 1;                   // Индекс правого ребёнка
            if right < length { // Если существуют оба ребёнка
                if sequence[left] < /*>*/ sequence[index + offset] || sequence[right] < /*>*/ sequence[index + offset] {
                    if sequence[left] < /*>*/ sequence[right] {
                        sequence.swap(index + offset, left);
                        flag = true;
                    } else if sequence[right] < /*>*/ sequence[left] {
                        sequence.swap(index + offset, right);
                        flag = true;
                    }
                }
                // Дополнительная проверка для последних двух элементов;
                // с её помощью можно отсортировать пирамиду состоящую всего лишь из трёх элементов
                if sequence[right] < /*>*/ sequence[left] {
                    sequence.swap(left, right);
                    flag = true;
                }
            } else if left < length { // Если существует только один ребёнок
                if sequence[left] < /*>*/ sequence[index + offset] {
                    sequence.swap(index + offset, left);
                    flag = true;
                }
            }
        }
        if flag {
            flag = false;
        } else {
            offset += 1; // Смещение увеличивается, когда на текущем этапе сортировать больше нечего
        }
        offset + 2 < length // Условие повторения цикла while
    } { /* Пустое тело цикла (имитация цикла с постусловием)*/ }
}

Вариант № 2

[править]

По сравнению с предыдущим вариантом элементы последовательности также должны быть копируемыми (реализовывать типаж Copy). 

fn heap_sort <T: PartialOrd + Copy> (sequence: &mut[T]) {
    fn sift_down <T: PartialOrd + Copy> (sequence: &mut[T], root: usize, limit: usize) {
        let mut parent = root;
        let mut child: usize;
        let item = sequence[root]; // Элемент, для которого ищется место в последовательности
        while {
            child = (parent << 1) + 1;
            child < limit // Условие повторения № 1: у sequence[parent] есть хоть один ребёнок
        } && {
            // Выбор большего /*меньшего*/ из детей sequence[parent]
            if child + 1 < limit && sequence[child] < /*>*/ sequence[child + 1] {
                child += 1;
            };
            item < /*>*/ sequence[child] // Условие повторения № 2: item меньше наибольшего /*больше наименьшего*/ из детей sequence[parent]
        } { // Тело цикла
            sequence[parent] = sequence[child]; // Сдвигаем ребёнка на место его родителя
            parent = child;
        }
        if parent > root { // Если в ходе предыдущей отработки цикла делались сдвиги
            sequence[parent] = item;  // Перемещаем item на найденное для него место
        }        
    };
    // Формирование первичной пирамиды
    let length = sequence.len();
    let mut index = length >> 1; // Индекс родителя последнего элемента последовательности
    while index > 0 {
        index -= 1;
        sift_down(sequence, index, length);
    }
    // Окончательное упорядочение
    index = length;
    while index > 1 {
        index -= 1;
        sequence.swap(0, index); // Обмен крайних элементов неупорядоченной части последовательности
        sift_down(sequence, 0, index); // Восстановление свойства пирамиды в неупорядоченной части последовательности
    }
}
Источник — https://ru.wikibooks.org/w/index.php?title=Реализации_алгоритмов/Сортировка/Пирамидальная&oldid=163406