Время работы алгоритма сортировки бинарной кучей в худшем случае

Сортировка кучей, пирамидальная сортировка (англ. Heapsort) — алгоритм сортировки, использующий структуру данных двоичная куча. Это неустойчивый алгоритм сортировки с временем работы , где — количество элементов для сортировки, и использующий дополнительной памяти.

Алгоритм

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

Реализация

• — массив, который необходимо отсортировать
• — количество элементов в нём
• — процедура, которая строит из передаваемого массива кучу для максимума в этом же массиве
• — процедура, которая просеивает вниз элемент в куче из элементов, находящихся в начале массива

 fun heapSort(A : list <T>):
   buildHeap(A)
   heapSize = A.size
   for i = 0 to n - 1
     swap(A[0], A[n - 1 - i])
     heapSize--
     siftDown(A, 0, heapSize)

Сложность

Операция работает за . Всего цикл выполняется раз. Таким образом сложность сортировки кучей является .

Достоинства:

• худшее время работы — ,
• требует дополнительной памяти.

Недостатки:

• неустойчивая,
• на почти отсортированных данных работает столь же долго, как и на хаотических данных.

Пример

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

JSort

JSort является модификацией сортировки кучей, которую придумал Джейсон Моррисон (Jason Morrison).
Алгоритм частично упорядочивает массив, строя на нём два раза кучу: один раз передвигая меньшие элементы влево, второй раз передвигая большие элементы вправо. Затем к массиву применяется
сортировка вставками, которая при почти отсортированных данных работает за .

Достоинства:

• В отличие от сортировки кучей, на почти отсортированных массивах работает быстрее, чем на случайных.
• В силу использования сортировки вставками, которая просматривает элементы последовательно, использование кэша гораздо эффективнее.

Недостатки:

• На длинных массивах, возникают плохо отсортированные последовательности в середине массива, что приводит к ухудшению работы сортировки вставками.

Алгоритм

Построим кучу для минимума на этом массиве.
Тогда наименьший элемент окажется на первой позиции, а левая часть массива окажется почти отсортированной, так как ей будут соответствовать верхние узлы кучи.
Теперь построим на этом же массиве кучу так, чтобы немного упорядочить правую часть массива. Эта куча должна быть кучей для максимума и быть «зеркальной» к массиву, то есть чтобы её корень соответствовал последнему элементу массива.
К получившемуся массиву применим сортировку вставками.

Сложность

Построение кучи занимает . Почти упорядоченный массив сортировка вставками может отсортировать , но в худшем случае за .

Таким образом, наихудшая оценка Jsort — .

Пример

Рассмотрим, массив =

Построим на этом массиве кучу для минимума:

Массив выглядит следующим образом:

Заметим, что начало почти упорядочено, что хорошо скажется на использовании сортировки вставками.

Построим теперь зеркальную кучу для максимума на этом же массиве.

Массив будет выглядеть следующим образом:

Теперь и конец массива выглядит упорядоченным, применим сортировку вставками и получим отсортированный массив.

См. также

• Сортировка слиянием
• Быстрая сортировка
• Теорема о нижней оценке для сортировки сравнениями

Источники информации

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. Издательский дом «Вильямс», 2005. ISBN 5-8459-0857-4
• Wikipedia — Heapsort
• Wikipedia — JSort
• Хабрахабр — Описание сортировки кучей и JSort
• Википедия — Пирамидальная сортировка

Сортировка кучей — популярный и эффективный алгоритм сортировки в компьютерном программировании. Чтобы научиться писать алгоритм сортировки кучей, требуется знание двух типов структур данных — массивов и деревьев.

Например, начальный набор чисел, которые мы хотим отсортировать, хранится в массиве [10, 3, 76, 34, 23, 32], и после сортировки мы получаем отсортированный массив [3,10,23,32,34,76].

Сортировка кучей работает путем визуализации элементов массива как особого вида полного двоичного дерева, называемого кучей.

Что такое бинарное дерево? Какие виды бинарных деревьев существуют?

Бинарное дерево

— это структура данных дерева, в которой каждый родительский узел может иметь не более двух дочерних элементов.

Полное бинарное дерево

— это особый тип бинарного дерева, в котором у каждого родительского узла есть два или нет дочерних элементов.

Идеальное бинарное дерево

похоже на полное бинарное дерево, но с двумя основными отличиями:

1. Каждый уровень должен быть полностью заполнен.
2. Все элементы листа должны наклоняться влево.

Примечание: Последний элемент может не иметь правильного брата, то есть идеальное бинарное дерево не обязательно должно быть полным бинарным деревом.

Как создать полное бинарное дерево из несортированного списка (массива)?

• Выберите первый элемент списка, чтобы он быть корневым узлом. (Первый уровень — 1 элемент).
• Поместите второй элемент в качестве левого дочернего элемента корневого узла, а третий элемент — в качестве правого дочернего элемента. (Второй уровень — 2 элемента).
• Поместите следующие два элемента в качестве дочерних элементов левого узла второго уровня. Снова, поместите следующие два элемента как дочерние элементы правого узла второго уровня (3-й уровень — 4 элемента).
• Продолжайте повторять, пока не дойдете до последнего элемента.

Связь между индексами массива и элементами дерева

Полное бинарное дерево обладает интересным свойством, которое мы можем использовать для поиска дочерних элементов и родителей любого узла.

Если индекс любого элемента в массиве равен i, элемент в индексе 2i + 1 станет левым потомком, а элемент в индексе 2i + 2 станет правым потомком. Кроме того, родительский элемент любого элемента с индексом i задается нижней границей (i-1) / 2.

Проверим это:

Left child of 1 (index 0)
= element in (2*0+1) index 
= element in 1 index 
= 12


Right child of 1
= element in (2*0+2) index
= element in 2 index 
= 9

Similarly,
Left child of 12 (index 1)
= element in (2*1+1) index
= element in 3 index
= 5

Right child of 12
= element in (2*1+2) index
= element in 4 index
= 6


  Также подтвердим, что правила верны для нахождения родителя любого узла:
 
Parent of 9 (position 2) 
= (2-1)/2 
= ½ 
= 0.5
~ 0 index 
= 1

Parent of 12 (position 1) 
= (1-1)/2 
= 0 index 
= 1


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

  Что такое структура данных кучи?

 

  Куча — это специальная древовидная структура данных. Говорят, что двоичное дерево следует структуре данных кучи, если
 


   это полное бинарное дерево;
  

   все узлы в дереве следуют тому свойству, что они больше своих потомков, то есть самый большой элемент находится в корне, и оба его потомка меньше, чем корень, и так далее. Такая куча называется убывающая куча (Max-Heap). Если вместо этого все узлы меньше своих потомков, это называется возрастающая куча (Min-Heap).
  




  Слева на рисунке убывающая куча, справа — возрастающая куча.
 


  Как выстроить дерево

 

  Начиная с идеального бинарного дерева, мы можем изменить его, чтобы оно стало убывающим, запустив функцию heapify для всех неконечных элементов кучи.
 



  


                       
  





  Поскольку heapfiy использует рекурсию, это может быть трудно для понимания. Итак, давайте сначала подумаем о том, как бы вы сложили дерево из трех элементов.
 
heapify(array)
    Root = array[0]
    Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])
    if(Root != Largest)
          Swap(Root, Largest)



  В приведенном выше примере показаны два сценария — один, в котором корень является самым большим элементом, и нам не нужно ничего делать. И еще один, в котором корень имеет дочерний элемент большего размера, и нам нужно было поменять их местами, чтобы сохранить свойство убывающей кучи.

  

  Если вы раньше работали с рекурсивными алгоритмами, то вы поняли, что это должен быть базовый случай.
 

  Теперь давайте подумаем о другом сценарии, в котором существует более одного уровня.
 


  На рисунке оба поддерева корневого элемента второго уровня уже являются

  

  убывающими кучами.

  

  Верхний элемент не подходит под убывающую кучу, но все поддеревья являются убывабщими.

  

  Чтобы сохранить свойство убывания для всего дерева, нам нужно будет «протолкнуть» родителя вниз, пока он не достигнет своей правильной позиции.
 


  Таким образом, чтобы сохранить свойство убывания в дереве, где оба поддеревья являются убывающими, нам нужно многократно запускать heapify для корневого элемента, пока он не станет больше, чем его дочерние элементы, или он не станет листовым узлом.
 

  Мы можем объединить оба эти условия в одну функцию heapify следующим образом:
 
void heapify(int arr[], int n, int i)
{
   int largest = i;
   int l = 2*i + 1;
   int r = 2*i + 2;

   if (l < n && arr[l] > arr[largest])
     largest = l;

   if (right < n && arr[r] > arr[largest])
     largest = r;

   if (largest != i)
   {
     swap(arr[i], arr[largest]);

     // Recursively heapify the affected sub-tree
     heapify(arr, n, largest);
   }
}


  Эта функция работает как для базового случая, так и для дерева любого размера. Таким образом, мы можем переместить корневой элемент в правильное положение, чтобы поддерживать статус убывающей кучи для любого размера дерева, пока поддеревья являются убывающими.
 



  


                       
  





  Сборка убывающей кучи

 

  Чтобы собрать убывающую кучу из любого дерева, мы можем начать выстраивать каждое поддерево снизу вверх и получить убывающую кучу после применения функции ко всем элементам, включая корневой элемент.
 

  В случае полного дерева первый индекс неконечного узла определяется как n / 2 — 1. Все остальные узлы после этого являются листовыми узлами и, следовательно, не нуждаются в куче.
 

  Мы можем выстроить убывающую кучу так:
 
// Build heap (rearrange array)
   for (int i = n / 2 - 1; i >= 0; i--)
     heapify(arr, n, i);



  Как показано на диаграмме выше, мы начинаем с кучи самых маленьких деревьев и постепенно продвигаемся вверх, пока не достигнем корневого элемента.
 

  Процедуры для Heapsort

 


   Поскольку дерево удовлетворяет свойству убывающей, самый большой элемент сохраняется в корневом узле.
  

   Удалите корневой элемент и поместите в конец массива (n-я позиция). Поместите последний элемент дерева (кучу) в свободное место.
  

   Уменьшите размер кучи на 1 и снова укрупните корневой элемент, чтобы у вас был самый большой элемент в корне.
  

   Процесс повторяется до тех пор, пока все элементы списка не будут отсортированы.
  



  Код выглядит так:
 
for (int i=n-1; i>=0; i--)
   {
     // Переместить текущий корень в конец
     swap(arr[0], arr[i]);

     // вызовите максимальный heapify на уменьшенной куче
     heapify(arr, i, 0);
   }


  Представление

 

  Сортировка кучи имеет O (nlogn) временные сложности для всех случаев (лучший случай, средний случай и худший случай). В чем же причина? Высота полного бинарного дерева, содержащего n элементов, равна log (n).
 

  Как мы видели ранее, чтобы полностью накапливать элемент, чьи поддеревья уже являются убывабщими кучами, нам нужно продолжать сравнивать элемент с его левым и правым потомками и толкать его вниз, пока он не достигнет точки, где оба его потомка меньше его.
 

  В худшем случае нам потребуется переместить элемент из корневого узла в конечный узел, выполнив несколько сравнений и обменов log (n).
 



  


                       
  





  На этапе build_max_heap мы делаем это для n / 2 элементов, поэтому сложность шага build_heap в наихудшем случае равна n / 2 * log (n) ~ nlogn.
 

  На этапе сортировки мы обмениваем корневой элемент с последним элементом и подкачиваем корневой элемент. Для каждого элемента это снова занимает большое время, поскольку нам, возможно, придется перенести этот элемент от корня до листа. Поскольку мы повторяем операцию n раз, шаг heap_sort также nlogn.
 

  Кроме того, поскольку шаги build_max_heap и heap_sort выполняются один за другим, алгоритмическая сложность не умножается и остается в порядке nlogn.
 

  Также выполняется сортировка в O (1) пространстве сложности. По сравнению с быстрой сортировкой, в худшем случае (O (nlogn)). Быстрая сортировка имеет сложность O (n ^ 2) для худшего случая. Но в других случаях быстрая сортировка выполняется достаточно быстро. Introsort — это альтернатива heapsort, которая сочетает в себе quicksort и heapsort для сохранения преимуществ, таких как скорость heapsort в худшем случае и средняя скорость quicksort.
 

  Применение сортировки кучей

 

  Системы, связанные с безопасностью, и встроенные системы, такие как ядро ​​Linux, используют сортировку кучей из-за верхней границы O (n log n) времени работы Heapsort и постоянной верхней границы O (1) его вспомогательного хранилища.
 

  Хотя сортировка кучей имеет O (n log n) временную сложность даже для наихудшего случая, у нее нет больше приложений (по сравнению с другими алгоритмами сортировки, такими как быстрая сортировка, сортировка слиянием). Тем не менее, его базовая структура данных, куча, может быть эффективно использована, если мы хотим извлечь наименьший (или наибольший) из списка элементов без дополнительных затрат на сохранение оставшихся элементов в отсортированном порядке. Например, приоритетные очереди.
 

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

 


   Реализация C ++

  
// C++ program for implementation of Heap Sort
#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i)
{
   // Find largest among root, left child and right child
   int largest = i;
   int l = 2*i + 1;
   int r = 2*i + 2;

   if (l < n && arr[l] > arr[largest])
     largest = l;

   if (right < n && arr[r] > arr[largest])
     largest = r;

   // Swap and continue heapifying if root is not largest
   if (largest != i)
   {
     swap(arr[i], arr[largest]);
     heapify(arr, n, largest);
   }
}

// main function to do heap sort
void heapSort(int arr[], int n)
{
   // Build max heap
   for (int i = n / 2 - 1; i >= 0; i--)
     heapify(arr, n, i);

   // Heap sort
   for (int i=n-1; i>=0; i--)
   {
     swap(arr[0], arr[i]);

     // Heapify root element to get highest element at root again
     heapify(arr, i, 0);
   }
}

void printArray(int arr[], int n)
{
   for (int i=0; i<n; ++i)
     cout << arr[i] << " ";
   cout << "n";
}

int main()
{
   int arr[] = {1,12,9,5,6,10};
   int n = sizeof(arr)/sizeof(arr[0]);
   heapSort(arr, n);

   cout << "Sorted array is n";
   printArray(arr, n);
}



   Реализация на Java

  
// Java program for implementation of Heap Sort
public class HeapSort
{   

    public void sort(int arr[])
    {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
          heapify(arr, n, i);
        }


        // Heap sort
        for (int i=n-1; i>=0; i--)
        {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Heapify root element
            heapify(arr, i, 0);
        }
    }

    void heapify(int arr[], int n, int i)
    {
        // Find largest among root, left child and right child
        int largest = i; 
        int l = 2*i + 1; 
        int r = 2*i + 2;  

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        // Swap and continue heapifying if root is not largest
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i < n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }

    public static void main(String args[])
    {
        int arr[] = {1,12,9,5,6,10};

        HeapSort hs = new HeapSort();
        hs.sort(arr);

        System.out.println("Sorted array is");
        printArray(arr);
    }
}



   Реализация на Python (Python 3)

  
def heapify(arr, n, i):
    # Find largest among root and children
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2 

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    # If root is not largest, swap with largest and continue heapifying
    if largest != i:
        arr[i],arr[largest] = arr[largest],arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)

    # Build max heap
    for i in range(n, 0, -1):
        heapify(arr, n, i)


    for i in range(n-1, 0, -1):
        # swap
        arr[i], arr[0] = arr[0], arr[i]  

        #heapify root element
        heapify(arr, i, 0)


arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
    print ("%d" %arr[i])

Перевод статьи подготовлен специально для студентов курса «Алгоритмы для разработчиков».

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

Что такое двоичная куча?

Давайте сначала определим законченное двоичное дерево. Законченное двоичное дерево — это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, имеет полный набор узлов, и все листья расположены как можно левее (Источник Википедия).

Двоичная куча — это законченное двоичное дерево, в котором элементы хранятся в особом порядке: значение в родительском узле больше (или меньше) значений в его двух дочерних узлах. Первый вариант называется max-heap, а второй — min-heap. Куча может быть представлена двоичным деревом или массивом.

Почему для двоичной кучи используется представление на основе массива ?

Поскольку двоичная куча — это законченное двоичное дерево, ее можно легко представить в виде массива, а представление на основе массива является эффективным с точки зрения расхода памяти. Если родительский узел хранится в индексе I, левый дочерний элемент может быть вычислен как 2 I + 1, а правый дочерний элемент — как 2 I + 2 (при условии, что индексирование начинается с 0).

Алгоритм пирамидальной сортировки в порядке по возрастанию:

1. Постройте max-heap из входных данных.
2. На данном этапе самый большой элемент хранится в корне кучи. Замените его на последний элемент кучи, а затем уменьшите ее размер на 1. Наконец, преобразуйте полученное дерево в max-heap с новым корнем.
3. Повторяйте вышеуказанные шаги, пока размер кучи больше 1.

Как построить кучу?

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

Входные данные: 4, 10, 3, 5, 1
         4(0)
        /   
     10(1)   3(2)
    /   
 5(3)    1(4)
Числа в скобках представляют индексы в представлении данных в виде массива.
Применение процедуры heapify к индексу 1:
         4(0)
        /   
    10(1)    3(2)
    /   
5(3)    1(4)
Применение процедуры heapify к индексу 0:
        10(0)
        /  
     5(1)  3(2)
    /   
 4(3)    1(4)
Процедура heapify вызывает себя рекурсивно для создания кучи  сверху вниз.

Рекомендация: Пожалуйста, сначала решите задачу на “PRACTICE”, прежде чем переходить к решению.

C++

// Реализация пирамидальной сортировки на C++
#include <iostream>

using namespace std;

// Процедура для преобразования в двоичную кучу поддерева с корневым узлом i, что является
// индексом в arr[]. n - размер кучи

void heapify(int arr[], int n, int i)
{
    int largest = i;   
// Инициализируем наибольший элемент как корень
    int l = 2*i + 1; // левый = 2*i + 1
    int r = 2*i + 2; // правый = 2*i + 2

 // Если левый дочерний элемент больше корня
    if (l < n && arr[l] > arr[largest])
        largest = l;

   // Если правый дочерний элемент больше, чем самый большой элемент на данный момент
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // Если самый большой элемент не корень
    if (largest != i)
    {
        swap(arr[i], arr[largest]);

// Рекурсивно преобразуем в двоичную кучу затронутое поддерево
        heapify(arr, n, largest);
    }
}

// Основная функция, выполняющая пирамидальную сортировку
void heapSort(int arr[], int n)
{
  // Построение кучи (перегруппируем массив)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

   // Один за другим извлекаем элементы из кучи
    for (int i=n-1; i>=0; i--)
    {
        // Перемещаем текущий корень в конец
        swap(arr[0], arr[i]);

        // вызываем процедуру heapify на уменьшенной куче
        heapify(arr, i, 0);
    }
}

/* Вспомогательная функция для вывода на экран массива размера n*/
void printArray(int arr[], int n)
{
    for (int i=0; i<n; ++i)
        cout << arr[i] << " ";
    cout << "n";
}

// Управляющая программа
int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr)/sizeof(arr[0]);

    heapSort(arr, n);

    cout << "Sorted array is n";
    printArray(arr, n);
}

Java

// Реализация пирамидальной сортировки на Java
public class HeapSort
{
    public void sort(int arr[])
    {
        int n = arr.length;

        // Построение кучи (перегруппируем массив)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // Один за другим извлекаем элементы из кучи   
        for (int i=n-1; i>=0; i--)
        {
            // Перемещаем текущий корень в конец
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Вызываем процедуру heapify на уменьшенной куче
            heapify(arr, i, 0);
        }
    }

    // Процедура для преобразования в двоичную кучу поддерева с корневым узлом i, что является
// индексом в arr[]. n - размер кучи
     void heapify(int arr[], int n, int i)
    {
        int largest = i; // Инициализируем наибольший элемент как корень
        int l = 2*i + 1; // левый = 2*i + 1
        int r = 2*i + 2; // правый = 2*i + 2

           // Если левый дочерний элемент больше корня
        if (l < n && arr[l] > arr[largest])
            largest = l;

          // Если правый дочерний элемент больше, чем самый большой элемент на данный момент
        if (r < n && arr[r] > arr[largest])
            largest = r;
       // Если самый большой элемент не корень
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

          // Рекурсивно преобразуем в двоичную кучу затронутое поддерево
            heapify(arr, n, largest);
        }
    }

    /* Вспомогательная функция для вывода на экран массива размера n */
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }

    // Управляющая программа
    public static void main(String args[])
    {
        int arr[] = {12, 11, 13, 5, 6, 7};
        int n = arr.length;

        HeapSort ob = new HeapSort();
        ob.sort(arr);

        System.out.println("Sorted array is");
        printArray(arr);
    }
}

Python

# Реализация пирамидальной сортировки на Python

# Процедура для преобразования в двоичную кучу поддерева с корневым узлом i, что является индексом в arr[]. n - размер кучи
def heapify(arr, n, i):
    largest = i # Initialize largest as root
    l = 2 * i + 1   # left = 2*i + 1
    r = 2 * i + 2   # right = 2*i + 2

  # Проверяем существует ли левый дочерний элемент больший, чем корень

    if l < n and arr[i] < arr[l]:
        largest = l

    # Проверяем существует ли правый дочерний элемент больший, чем корень

    if r < n and arr[largest] < arr[r]:
        largest = r

    # Заменяем корень, если нужно
    if largest != i:
        arr[i],arr[largest] = arr[largest],arr[i] # свап

        # Применяем heapify к корню.
        heapify(arr, n, largest)

# Основная функция для сортировки массива заданного размера
def heapSort(arr):
    n = len(arr)

    # Построение max-heap.
    for i in range(n, -1, -1):
        heapify(arr, n, i)

    # Один за другим извлекаем элементы
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i] # свап 
        heapify(arr, i, 0)

# Управляющий код для тестирования
arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
    print ("%d" %arr[i]),
# Этот код предоставил Mohit Kumra

C Sharp

// Реализация пирамидальной сортировки на C#
using System;

public class HeapSort
{
    public void sort(int[] arr)
    {
        int n = arr.Length;

        // Построение кучи (перегруппируем массив)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

       // Один за другим извлекаем элементы из кучи
        for (int i=n-1; i>=0; i--)
        {
            // Перемещаем текущий корень в конец
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // вызываем процедуру heapify на уменьшенной куче
            heapify(arr, i, 0);
        }
    }

    // Процедура для преобразования в двоичную кучу поддерева с корневым узлом i, что является
// индексом в arr[]. n - размер кучи

    void heapify(int[] arr, int n, int i)
    {
        int largest = i;
// Инициализируем наибольший элемент как корень
        int l = 2*i + 1; // left = 2*i + 1
        int r = 2*i + 2; // right = 2*i + 2

        // Если левый дочерний элемент больше корня
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // Если правый дочерний элемент больше, чем самый большой элемент на данный момент
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // Если самый большой элемент не корень
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Рекурсивно преобразуем в двоичную кучу затронутое поддерево
            heapify(arr, n, largest);
        }
    }

    /* Вспомогательная функция для вывода на экран массива размера n */
    static void printArray(int[] arr)
    {
        int n = arr.Length;
        for (int i=0; i<n; ++i)
            Console.Write(arr[i]+" ");
        Console.Read();
    }

    //Управляющая программа
    public static void Main()
    {
        int[] arr = {12, 11, 13, 5, 6, 7};
        int n = arr.Length;

        HeapSort ob = new HeapSort();
        ob.sort(arr);

        Console.WriteLine("Sorted array is");
        printArray(arr);
    }
}

//Этот код предоставил
// Akanksha Ra (Abby_akku)

PHP

<?php

// Реализация пирамидальной сортировки на Php

// Процедура для преобразования в двоичную кучу поддерева с корневым узлом i, что является
// индексом в arr[]. n - размер кучи

function heapify(&$arr, $n, $i)
{
    $largest = $i; // Инициализируем наибольший элемент как корень
    $l = 2*$i + 1; // левый = 2*i + 1
    $r = 2*$i + 2; // правый = 2*i + 2

    // Если левый дочерний элемент больше корня
    if ($l < $n && $arr[$l] > $arr[$largest])
        $largest = $l;

    //Если правый дочерний элемент больше, чем самый большой элемент на данный момент
    if ($r < $n && $arr[$r] > $arr[$largest])
        $largest = $r;

    // Если самый большой элемент не корень
    if ($largest != $i)
    {
        $swap = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $swap;

        // Рекурсивно преобразуем в двоичную кучу затронутое поддерево
        heapify($arr, $n, $largest);
    }
}

//Основная функция, выполняющая пирамидальную сортировку
function heapSort(&$arr, $n)
{
    // Построение кучи (перегруппируем массив)
    for ($i = $n / 2 - 1; $i >= 0; $i--)
        heapify($arr, $n, $i);

    //Один за другим извлекаем элементы из кучи
    for ($i = $n-1; $i >= 0; $i--)
    {
        // Перемещаем текущий корень в конец
        $temp = $arr[0];
            $arr[0] = $arr[$i];
            $arr[$i] = $temp;

        // вызываем процедуру heapify на уменьшенной куче
        heapify($arr, $i, 0);
    }
}

/* Вспомогательная функция для вывода на экран массива размера n */
function printArray(&$arr, $n)
{
    for ($i = 0; $i < $n; ++$i)
        echo ($arr[$i]." ") ; 

} 

// Управляющая программа
    $arr = array(12, 11, 13, 5, 6, 7);
    $n = sizeof($arr)/sizeof($arr[0]);

    heapSort($arr, $n);

    echo 'Sorted array is ' . "n";

    printArray($arr , $n);

// Этот код предоставил Shivi_Aggarwal
?>

Вывод:

Отсортированный массив:
5 6 7 11 12 13

Здесь предыдущий C-код для справки.

Замечания:
Пирамидальная сортировка — это вполне годный алгоритм. Его типичная реализация не стабильна, но может быть таковой сделана (см. Здесь).

Временная сложность: Временная сложность heapify — O(Logn). Временная сложность createAndBuildHeap() равна O(n), а общее время работы пирамидальной сортировки — O(nLogn).

Применения пирамидальной сортировки:

1. Отсортировать почти отсортированный (или отсортированный на K позиций) массив ;
2. k самых больших (или самых маленьких) элементов в массиве.

Алгоритм пирамидальной сортировки имеет ограниченное применение, потому что Quicksort (Быстрая сортировка) и Mergesort (Сортировка слиянием) на практике лучше. Тем не менее, сама структура данных кучи используется довольно часто. См. Применения структуры данных кучи

Скриншоты:

— (Теперь, когда мы построили кучу, мы должны преобразовать ее в max-heap)

— (В max-heap родительский узел всегда больше или равен по отношению к дочерним
10 больше 4. Поэтому мы меняем местами 4 и 10)
— (В max-heap родительский узел всегда больше или равен по отношению к дочерним
5 больше 4. По этому мы меняем местами 5 и 4)

— (Меняем местами первый и последний узлы и удаляем последний из кучи)

Тест по пирамидальной сортировке

Другие алгоритмы сортировки на GeeksforGeeks/GeeksQuiz:
Быстрая сортировка, Сортировка выбором, Сортировка пузырьком, Сортировка вставками, Сортировка слиянием, Пирамидальная сортировка, Поразрядная сортировка, Сортировка подсчетом, Блочная сортировка, Сортировка Шелла, Сортировка расческой, Сортировка подсчетом со списком.

Практикум по сортировке

Пожалуйста, оставляйте комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Ал­го­ритм пи­ра­ми­даль­ной сор­ти­ров­ки по-ан­глий­ски на­зы­ва­ет­ся «Heap Sort». «Heap» пе­ре­во­дит­ся, как «ку­ча». В свя­зи с этим пи­ра­ми­даль­ную сор­ти­ров­ку ещё на­зы­ва­ют «сор­ти­ров­ка ку­чей»

Оста­вим в сто­ро­не ре­ли­ги­оз­ные спо­ры о пре­иму­ще­ствах и не­до­стат­ках ал­го­рит­ма Quick Sort, и бу­дем рас­смат­ри­вать пи­ра­ми­даль­ную сор­ти­ров­ку, как са­мый быст­рый ал­го­ритм из до­ступ­ных (см. Лек­цию №3) для сор­ти­ров­ки не­боль­ших объ­ё­мов дан­ных (уме­щаю­щих­ся в кеш про­цес­со­ра).

Пи­ра­ми­даль­ная сор­ти­ров­ка бы­ла пред­ло­же­на Дж. Уи­льям­сом в 1964 го­ду. Это ал­го­ритм сор­ти­ров­ки мас­си­ва про­из­воль­ных эле­мен­тов, не тре­бую­щий до­пол­ни­тель­ной па­мя­ти и до­пол­ни­тель­ных ст­рук­тур дан­ных. Вре­мя ра­бо­ты ал­го­рит­ма — в сред­нем, а так­же в луч­шем и худ­шем слу­ча­ях.

Вез­де в этой лек­ции бу­дем счи­тать, что пер­вый эле­мент мас­си­ва име­ет ин­декс 0.

Дво­ич­ное де­ре­во

Дво­ич­ное де­ре­во — ст­рук­ту­ра дан­ных, в ко­то­рой каж­дый эле­мент име­ет ле­во­го и/или пра­во­го по­том­ка, ли­бо во­об­ще не име­ет по­том­ков. В по­след­нем слу­чае эле­мент на­зы­ва­ет­ся ли­сто­вым.

Ес­ли эле­мент A име­ет по­том­ка B, то эле­мент A на­зы­ва­ет­ся ро­ди­те­лем эле­мен­та B. В дво­ич­ном де­ре­ве су­ще­ству­ет един­ствен­ный эле­мент, ко­то­рый не име­ет ро­ди­те­лей; та­кой эле­мент на­зы­ва­ет­ся кор­не­вым.

При­мер дво­ич­но­го де­ре­ва по­ка­зан на ри­сун­ке 1:

По­чти за­пол­нен­ным дво­ич­ным де­ре­вом на­зы­ва­ет­ся дво­ич­ное де­ре­во, об­ла­даю­щее тре­мя свой­ства­ми:

1. все ли­сто­вые эле­мен­ты на­хо­дят­ся в ниж­нем уров­не, ли­бо в ниж­них двух уров­нях;
2. все ли­стья в уров­не за­пол­ня­ют уро­вень сле­ва;
3. все уров­ни (кро­ме, быть мо­жет, по­след­не­го уров­ня) пол­но­стью за­пол­не­ны эле­мен­та­ми.

Де­ре­во на рис. 1 не яв­ля­ет­ся по­чти за­пол­нен­ным, так как уро­вень 4 не за­пол­нен сле­ва (эле­мент g «ме­ша­ет»), и тре­тий уро­вень (не яв­ляю­щий­ся по­след­ним), не за­пол­нен пол­но­стью.

По­чти за­пол­нен­ное дво­ич­ное де­ре­во мож­но хра­нить в мас­си­ве без до­пол­ни­тель­ных за­трат. Для это­го до­ста­точ­но пе­ре­ну­ме­ро­вать эле­мен­ты каж­до­го уров­ня сле­ва-на­пра­во:

Не­труд­но ви­деть, что при та­кой ну­ме­ра­ции по­том­ки уз­ла с но­ме­ром n (ес­ли есть) име­ют но­ме­ра  и . Ро­ди­тель уз­ла име­ет но­мер :

Пи­ра­ми­да

Воз­рас­таю­щей пи­ра­ми­дой на­зы­ва­ет­ся по­чти за­пол­нен­ное де­ре­во, в ко­то­ром зна­че­ние каж­до­го эле­мен­та боль­ше ли­бо рав­но зна­че­ния всех его по­том­ков. Ана­ло­гич­но, в убы­ваю­щей пи­ра­ми­де зна­че­ние каж­до­го эле­мен­та мень­ше ли­бо рав­но зна­че­ния по­том­ков.

При­мер воз­рас­таю­щей пи­ра­ми­ды по­ка­зан на ри­сун­ке:

Оче­вид­но, са­мое боль­шое зна­че­ние в воз­рас­таю­щей пи­ра­ми­де име­ет кор­не­вой эле­мент. Од­на­ко, из свойств пи­ра­ми­ды не сле­ду­ет, что зна­че­ния эле­мен­тов умень­ша­ют­ся с уве­ли­че­ни­ем уров­ня. В част­но­сти, на рис. 4 эле­мент со зна­че­ни­ем 3 на чет­вёр­том уров­не боль­ше зна­че­ний всех эле­мен­тов, кро­ме од­но­го, на тре­тьем уров­не.

Важ­ной опе­ра­ци­ей яв­ля­ет­ся от­де­ле­ние по­след­не­го (в смыс­ле ну­ме­ра­ции) эле­мен­та от пи­ра­ми­ды. Не­труд­но до­ка­зать, что в этом слу­чае дво­ич­ное де­ре­во оста­ёт­ся по­чти за­пол­нен­ным, и все свой­ства пи­ра­ми­ды со­хра­ня­ют­ся.

Про­сеи­ва­ние вверх

Рас­смот­рим те­перь за­да­чу при­со­еди­не­ния эле­мен­та с про­из­воль­ным зна­че­ни­ем к воз­рас­таю­щей пи­ра­ми­де. Ес­ли про­сто до­ба­вить эле­мент в ко­нец мас­си­ва, то свой­ство пи­ра­ми­ды (зна­че­ние лю­бо­го эле­мен­та  зна­че­ния его ро­ди­те­ля) мо­жет быть на­ру­ше­но. Для вос­ста­нов­ле­ния свой­ства пи­ра­ми­ды к до­бав­лен­но­му эле­мен­ту при­ме­ня­ет­ся про­це­ду­ра про­сеи­ва­ния вверх, ко­то­рая опи­сы­ва­ет­ся сле­дую­щим ал­го­рит­мом:

1. ес­ли эле­мент кор­не­вой, или его зна­че­ние  зна­че­ния ро­ди­те­ля, то ко­нец;
2. ме­ня­ем ме­ста­ми зна­че­ния эле­мен­та и его ро­ди­те­ля;
3. вы­пол­ня­ем про­це­ду­ру про­сеи­ва­ния вверх для ро­ди­те­ля.

По­сле вы­пол­не­ния дан­ной про­це­ду­ры свой­ство пи­ра­ми­ды бу­дет вос­ста­нов­ле­но, так как:

• Ес­ли вновь до­бав­лен­ный эле­мент боль­ше ро­ди­те­ля, то он боль­ше и вто­ро­го по­том­ка ро­ди­те­ля, так как до до­бав­ле­ния но­во­го эле­мен­та бы­ло вы­пол­не­но свой­ство пи­ра­ми­ды, и ро­ди­тель был не мень­ше сво­е­го по­том­ка. По­это­му по­сле об­ме­на зна­че­ний эле­мен­та и ро­ди­те­ля свой­ство пи­ра­ми­ды бу­дет вос­ста­нов­ле­но в под­де­ре­ве, кор­нем ко­то­ро­го яв­ля­ет­ся ро­ди­тель с но­вым зна­че­ни­ем.
• Но свой­ство пи­ра­ми­ды мо­жет быть на­ру­ше­но в от­но­ше­нии ро­ди­те­ля и ро­ди­те­ля ро­ди­те­ля (так как зна­че­ние ро­ди­те­ля ста­ло боль­ше). Про­це­ду­ра вы­зы­ва­ет­ся для ро­ди­тель­ско­го уз­ла, что­бы вос­ста­но­вить это свой­ство.

Ис­ход­ный код про­це­ду­ры про­сеи­ва­ния вверх я не при­во­жу, так как он нам не по­на­до­бит­ся. При­мер про­сеи­ва­ния вверх по­ка­зан на ри­сун­ке:

Про­сеи­ва­ние вниз

Что де­лать, ес­ли нам нуж­но за­ме­нить кор­не­вой эле­мент на ка­кой-ли­бо дру­гой? В этом слу­чае пи­ра­ми­даль­ную ст­рук­ту­ру дво­ич­но­го де­ре­ва мож­но вос­ста­но­вить с по­мо­щью про­це­ду­ры про­сеи­ва­ния вниз:

1. ес­ли эле­мент ли­сто­вой, или его зна­че­ние зна­че­ний по­том­ков, то ко­нец;
2. ме­ня­ем ме­ста­ми зна­че­ния эле­мен­та и его по­том­ка, имею­ще­го мак­си­маль­ное зна­че­ние;
3. вы­пол­ня­ем про­це­ду­ру про­сеи­ва­ния вниз для из­ме­нив­ше­го­ся по­том­ка.

Ис­ход­ный код про­це­ду­ры про­сеи­ва­ния вниз при­ве­дён в ли­стин­ге 1:

При­мер про­сеи­ва­ния вниз по­ка­зан на ри­сун­ке:

По­строе­ние пи­ра­ми­ды

До­пу­стим, у нас есть про­из­воль­ный на­бор из n эле­мен­тов, и мы хо­тим по­стро­ить из не­го пи­ра­ми­ду. Са­мый про­стой спо­соб это­го до­бить­ся — на­чать с пу­стой пи­ра­ми­ды, и до­бав­лять в неё эле­мен­ты один за дру­гим, каж­дый раз вы­зы­вая про­це­ду­ру про­сеи­ва­ния вверх для но­во­го эле­мен­та. На­зо­вём этот ме­тод по­строе­ния пи­ра­ми­ды «ме­то­дом про­сеи­ва­ния вверх». При­мер ра­бо­ты ал­го­рит­ма по­ка­зан на ри­сун­ке:

Рас­счи­та­ем быст­ро­дей­ствие это­го ме­то­да в са­мом пло­хом слу­чае. Пусть мас­сив уже от­сор­ти­ро­ван по воз­рас­та­нию, и каж­дый до­бав­ляе­мый эле­мент вы­нуж­ден про­сеи­вать­ся вверх до са­мо­го кор­ня. То­гда при до­бав­ле­нии эле­мен­та но­мер i нам по­тре­бу­ет­ся  опе­ра­ций. Мы де­ла­ем эту про­це­ду­ру для всех i от 0 до :

(1)

Оце­ним сум­му в вы­ра­же­нии (1) с по­мо­щью опре­де­лён­но­го ин­тег­ра­ла:

(2)

Вы­чис­ляя ин­тег­ра­лы, по­лу­ча­ем:

(3)

Это озна­ча­ет, что:

(4)

На са­мом де­ле пи­ра­ми­ду мож­но по­стро­ить быст­рее. Для это­го за­пол­ним де­ре­во эле­мен­та­ми в слу­чай­ном по­ряд­ке (на­при­мер так, как они идут в мас­си­ве из­на­чаль­но), и бу­дем его ис­прав­лять.

За­ме­тим, что ес­ли у нас есть две пи­ра­ми­ды, то, ес­ли их со­еди­нить об­щим кор­нем, а за­тем про­се­ять ко­рень вниз, то мы по­лу­чим но­вую боль­шую пи­ра­ми­ду. Де­ре­вья, со­сто­я­щие из од­но­го эле­мен­та, за­ве­до­мо яв­ля­ют­ся пи­ра­ми­да­ми, по­это­му нач­нём с на­бо­ра ли­сто­вых эле­мен­тов, а за­тем бу­дем со­еди­нять имею­щие­ся пи­ра­ми­ды по­пар­но до тех пор, по­ка не по­лу­чим од­ну боль­шую пи­ра­ми­ду. Пер­вый до­бав­ляе­мый ко­рень име­ет ин­декс . Ал­го­ритм сле­дую­щий: «для всех i от  до 0 вы­зы­ва­ем про­це­ду­ру про­сеи­ва­ния эле­мен­та вниз». На­зо­вём этот ме­тод по­строе­ния пи­ра­ми­ды «ме­то­дом про­сеи­ва­ния вниз».

Вы­чис­лим быст­ро­дей­ствие это­го ал­го­рит­ма в худ­шем слу­чае. Пусть мас­сив от­сор­ти­ро­ван по воз­рас­та­нию, и каж­дый до­бав­ляе­мый ко­рень дол­жен быть про­се­ян в са­мый низ. Вы­со­та де­ре­ва при­мер­но рав­на , глу­би­на за­ле­га­ния эле­мен­та но­мер i в де­ре­ве рав­на , по­это­му он бу­дет про­сеи­вать­ся вниз ша­гов. То­гда об­щее вре­мя по­строе­ния пи­ра­ми­ды бу­дет рав­но:

(5)

Оце­ни­вая сум­му ин­тег­ра­ла­ми ана­ло­гич­но (2), (3), по­лу­чим:

(6)

В даль­ней­шем бу­дем стро­ить пи­ра­ми­ду ме­то­дом про­сеи­ва­ния вниз.

Сор­ти­ров­ка

Имея по­стро­ен­ную пи­ра­ми­ду, не­слож­но реа­ли­зо­вать сор­ти­ров­ку. Так как кор­не­вой узел пи­ра­ми­ды име­ет са­мое боль­шое зна­че­ние, мы мо­жем от­де­лить его и по­ме­стить в ко­нец мас­си­ва. Вме­сто кор­не­во­го уз­ла мож­но по­ста­вить по­след­ний узел де­ре­ва и, про­се­яв его вниз, сно­ва по­лу­чить пи­ра­ми­ду. В но­вом де­ре­ве ко­рень име­ет са­мое боль­шое зна­че­ние сре­ди остав­ших­ся эле­мен­тов. Его сно­ва мож­но от­де­лить, и так да­лее. Ал­го­ритм по­лу­ча­ет­ся сле­дую­щий:

1. по­ме­нять ме­ста­ми зна­че­ния пер­во­го и по­след­не­го уз­лов пи­ра­ми­ды;
2. от­де­лить по­след­ний узел от де­ре­ва, умень­шив раз­мер де­ре­ва на еди­ни­цу (эле­мент оста­ёт­ся в мас­си­ве);
3. вос­ста­но­вить пи­ра­ми­ду, про­се­яв вниз её но­вый кор­не­вой эле­мент;
4. пе­рей­ти к пунк­ту 1;

По ме­ре ра­бо­ты ал­го­рит­ма, часть мас­си­ва, за­ня­тая де­ре­вом, умень­ша­ет­ся, а в кон­це мас­си­ва на­кап­ли­ва­ет­ся от­сор­ти­ро­ван­ный ре­зуль­тат.

Реа­ли­за­ция пи­ра­ми­даль­ной сор­ти­ров­ки на язы­ке про­грам­ми­ро­ва­ния C++ при­ве­де­на в ли­стин­ге 2 (ис­поль­зу­ет­ся про­це­ду­ра про­сеи­ва­ния вниз из ли­стин­га 1):

Тео­ре­ти­че­ское вре­мя ра­бо­ты это­го ал­го­рит­ма не­труд­но оце­нить, ес­ли за­ме­тить, что пи­ра­ми­даль­ная сор­ти­ров­ка (без учё­та на­чаль­но­го по­строе­ния пи­ра­ми­ды) пол­но­стью ана­ло­гич­на по­строе­нию пи­ра­ми­ды ме­то­дом про­сеи­ва­ния вверх, толь­ко про­из­во­дит­ся «в об­рат­ном по­ряд­ке»: пи­ра­ми­да не стро­ит­ся, а «раз­би­ра­ет­ся» эле­мент-за-эле­мен­том, и эле­мен­ты про­сеи­ва­ют­ся не вверх, а вниз. По­это­му вре­мя ра­бо­ты ал­го­рит­ма пи­ра­ми­даль­ной сор­ти­ров­ки  без учё­та вре­ме­ни по­строе­ния пи­ра­ми­ды бу­дет опре­де­лять­ся ана­ло­гич­но фор­му­ле (4):

(7)

То­гда об­щее вре­мя сор­ти­ров­ки (с учё­том по­строе­ния пи­ра­ми­ды) бу­дет рав­но:

(8)

Из­ме­ре­ние быст­ро­дей­ствия ал­го­рит­ма

Мы уже вы­яс­ни­ли с по­мо­щью тео­ре­ти­че­ских оце­нок, что вре­мя ра­бо­ты ал­го­рит­ма пи­ра­ми­даль­ной сор­ти­ров­ки рав­но: . По­лез­но так­же знать, че­му ра­вен не­из­ве­ст­ный ко­эф­фи­ци­ент пе­ред  при вы­пол­не­нии сор­ти­ров­ки на ре­аль­ной вы­чис­ли­тель­ной си­сте­ме.

На рис. 8 по­ка­зан гра­фик ве­ли­чи­ны , опре­де­ля­е­мой вы­ра­же­ни­ем:

(9)

где n — ко­ли­че­ство сор­ти­руе­мых псев­до­слу­чай­ных че­ты­рёх­бай­то­вых це­лых чи­сел,  — вре­мя сор­ти­ров­ки на мо­ём ком­пью­те­ре.

Мой про­цес­сор: Intel Mobile Core 2 Duo T7500 (во вре­мя те­стов про­грам­ма ра­бо­та­ла на од­ном яд­ре). Так­то­вая ча­сто­та: 2.2 ГГц. Кэш L2: 4 МБ, 16-ас­со­ци­а­тив­ный, 64 бай­та на стро­ку.

Для каж­до­го чис­ла эле­мен­тов бы­ло вы­пол­не­но во­семь те­стов, и из их ре­зуль­та­тов был взят ми­ни­мум, что­бы ис­клю­чить слу­чай­ное влия­ние дру­гих вы­чис­ли­тель­ных за­дач на ход экс­пе­ри­мен­та.

На гра­фи­ке про­яв­ля­ют­ся две важ­ные осо­бен­но­сти ал­го­рит­ма:

1. Ал­го­ритм от­но­си­тель­но мед­лен­но ра­бо­та­ет, ко­гда чис­ло сор­ти­руе­мых эле­мен­тов мень­ше сот­ни. Для ма­ло­го чис­ла эле­мен­тов же­ла­тель­но ис­поль­зо­вать сор­ти­ро­воч­ные се­ти; об этом я рас­ска­жу в од­ной из сле­дую­щих лек­ций.
2. Ко­гда ко­ли­че­ство сор­ти­руе­мых дан­ных на­чи­на­ет пре­вы­шать раз­мер кэ­ша (в на­шем слу­чае мил­ли­он чи­сел по 4 бай­та), ско­рость сор­ти­ров­ки па­да­ет. Это вы­зва­но тем, что ал­го­ритм об­ра­ща­ет­ся к эле­мен­там мас­си­ва до­воль­но слу­чай­ным об­ра­зом (с точ­ки зре­ния ал­го­рит­ма ра­бо­ты ке­ша). По ме­ре то­го, как всё мень­шая часть дан­ных умень­ша­ет­ся в ке­ше, ско­рость ра­бо­ты ал­го­рит­ма всё бо­лее опре­де­ля­ет­ся ско­ро­стью ра­бо­ты опе­ра­тив­ной па­мя­ти, а не ско­ро­стью ра­бо­ты ке­ша. В од­ной из сле­дую­щих лек­ций мы устра­ним этот не­до­ста­ток.

Heap Sort is a popular and efficient sorting algorithm in computer programming. Learning how to write the heap sort algorithm requires knowledge of two types of data structures — arrays and trees.

The initial set of numbers that we want to sort is stored in an array e.g. [10, 3, 76, 34, 23, 32] and after sorting, we get a sorted array [3,10,23,32,34,76].

Heap sort works by visualizing the elements of the array as a special kind of complete binary tree called a heap.

Note: As a prerequisite, you must know about a complete binary tree and heap data structure.

Relationship between Array Indexes and Tree Elements

A complete binary tree has an interesting property that we can use to find the children and parents of any node.

If the index of any element in the array is i, the element in the index 2i+1 will become the left child and element in 2i+2 index will become the right child. Also, the parent of any element at index i is given by the lower bound of (i-1)/2.

Let’s test it out,

Left child of 1 (index 0)
= element in (2*0+1) index 
= element in 1 index 
= 12


Right child of 1
= element in (2*0+2) index
= element in 2 index 
= 9

Similarly,
Left child of 12 (index 1)
= element in (2*1+1) index
= element in 3 index
= 5

Right child of 12
= element in (2*1+2) index
= element in 4 index
= 6

Let us also confirm that the rules hold for finding parent of any node

Parent of 9 (position 2) 
= (2-1)/2 
= ½ 
= 0.5
~ 0 index 
= 1

Parent of 12 (position 1) 
= (1-1)/2 
= 0 index 
= 1

Understanding this mapping of array indexes to tree positions is critical to understanding how the Heap Data Structure works and how it is used to implement Heap Sort.

What is Heap Data Structure?

Heap is a special tree-based data structure. A binary tree is said to follow a heap data structure if

• it is a complete binary tree
• All nodes in the tree follow the property that they are greater than their children i.e. the largest element is at the root and both its children and smaller than the root and so on. Such a heap is called a max-heap. If instead, all nodes are smaller than their children, it is called a min-heap

The following example diagram shows Max-Heap and Min-Heap.

To learn more about it, please visit Heap Data Structure.

How to «heapify» a tree

Starting from a complete binary tree, we can modify it to become a Max-Heap by running a function called heapify on all the non-leaf elements of the heap.

Since heapify uses recursion, it can be difficult to grasp. So let’s first think about how you would heapify a tree with just three elements.

heapify(array)
    Root = array[0]
    Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])
    if(Root != Largest)
          Swap(Root, Largest)

The example above shows two scenarios — one in which the root is the largest element and we don’t need to do anything. And another in which the root had a larger element as a child and we needed to swap to maintain max-heap property.

If you’re worked with recursive algorithms before, you’ve probably identified that this must be the base case.

Now let’s think of another scenario in which there is more than one level.

The top element isn’t a max-heap but all the sub-trees are max-heaps.

To maintain the max-heap property for the entire tree, we will have to keep pushing 2 downwards until it reaches its correct position.

Thus, to maintain the max-heap property in a tree where both sub-trees are max-heaps, we need to run heapify on the root element repeatedly until it is larger than its children or it becomes a leaf node.

We can combine both these conditions in one heapify function as

void heapify(int arr[], int n, int i) {
  // Find largest among root, left child and right child
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest])
    largest = left;

  if (right < n && arr[right] > arr[largest])
    largest = right;

    // Swap and continue heapifying if root is not largest
    if (largest != i) {
      swap(&arr[i], &arr[largest]);
      heapify(arr, n, largest);
  }
}

This function works for both the base case and for a tree of any size. We can thus move the root element to the correct position to maintain the max-heap status for any tree size as long as the sub-trees are max-heaps.

Build max-heap

To build a max-heap from any tree, we can thus start heapifying each sub-tree from the bottom up and end up with a max-heap after the function is applied to all the elements including the root element.

In the case of a complete tree, the first index of a non-leaf node is given by n/2 - 1. All other nodes after that are leaf-nodes and thus don’t need to be heapified.

So, we can build a maximum heap as

    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);

As shown in the above diagram, we start by heapifying the lowest smallest trees and gradually move up until we reach the root element.

If you’ve understood everything till here, congratulations, you are on your way to mastering the Heap sort.

Working of Heap Sort

1. Since the tree satisfies Max-Heap property, then the largest item is stored at the root node.
2. Swap: Remove the root element and put at the end of the array (nth position) Put the last item of the tree (heap) at the vacant place.
3. Remove: Reduce the size of the heap by 1.
4. Heapify: Heapify the root element again so that we have the highest element at root.
5. The process is repeated until all the items of the list are sorted.

The code below shows the operation.

    // Heap sort
    for (int i = n - 1; i >= 0; i--) {
      swap(&arr[0], &arr[i]);

      // Heapify root element to get highest element at root again
      heapify(arr, i, 0);
    }

# Heap Sort in python


  def heapify(arr, n, i):
      # Find largest among root and children
      largest = i
      l = 2 * i + 1
      r = 2 * i + 2
  
      if l < n and arr[i] < arr[l]:
          largest = l
  
      if r < n and arr[largest] < arr[r]:
          largest = r
  
      # If root is not largest, swap with largest and continue heapifying
      if largest != i:
          arr[i], arr[largest] = arr[largest], arr[i]
          heapify(arr, n, largest)
  
  
  def heapSort(arr):
      n = len(arr)
  
      # Build max heap
      for i in range(n//2, -1, -1):
          heapify(arr, n, i)
  
      for i in range(n-1, 0, -1):
          # Swap
          arr[i], arr[0] = arr[0], arr[i]
  
          # Heapify root element
          heapify(arr, i, 0)
  
  
  arr = [1, 12, 9, 5, 6, 10]
  heapSort(arr)
  n = len(arr)
  print("Sorted array is")
  for i in range(n):
      print("%d " % arr[i], end='')
  

// Heap Sort in Java
  
  public class HeapSort {
  
    public void sort(int arr[]) {
      int n = arr.length;
  
      // Build max heap
      for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
      }
  
      // Heap sort
      for (int i = n - 1; i >= 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
  
        // Heapify root element
        heapify(arr, i, 0);
      }
    }
  
    void heapify(int arr[], int n, int i) {
      // Find largest among root, left child and right child
      int largest = i;
      int l = 2 * i + 1;
      int r = 2 * i + 2;
  
      if (l < n && arr[l] > arr[largest])
        largest = l;
  
      if (r < n && arr[r] > arr[largest])
        largest = r;
  
      // Swap and continue heapifying if root is not largest
      if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
  
        heapify(arr, n, largest);
      }
    }
  
    // Function to print an array
    static void printArray(int arr[]) {
      int n = arr.length;
      for (int i = 0; i < n; ++i)
        System.out.print(arr[i] + " ");
      System.out.println();
    }
  
    // Driver code
    public static void main(String args[]) {
      int arr[] = { 1, 12, 9, 5, 6, 10 };
  
      HeapSort hs = new HeapSort();
      hs.sort(arr);
  
      System.out.println("Sorted array is");
      printArray(arr);
    }
  }

// Heap Sort in C
  
  #include <stdio.h>
  
  // Function to swap the the position of two elements
  void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
  }
  
  void heapify(int arr[], int n, int i) {
    // Find largest among root, left child and right child
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
  
    if (left < n && arr[left] > arr[largest])
      largest = left;
  
    if (right < n && arr[right] > arr[largest])
      largest = right;
  
    // Swap and continue heapifying if root is not largest
    if (largest != i) {
      swap(&arr[i], &arr[largest]);
      heapify(arr, n, largest);
    }
  }
  
  // Main function to do heap sort
  void heapSort(int arr[], int n) {
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);
  
    // Heap sort
    for (int i = n - 1; i >= 0; i--) {
      swap(&arr[0], &arr[i]);
  
      // Heapify root element to get highest element at root again
      heapify(arr, i, 0);
    }
  }
  
  // Print an array
  void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
      printf("%d ", arr[i]);
    printf("n");
  }
  
  // Driver code
  int main() {
    int arr[] = {1, 12, 9, 5, 6, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
  
    heapSort(arr, n);
  
    printf("Sorted array is n");
    printArray(arr, n);
  }

// Heap Sort in C++
  
  #include <iostream>
  using namespace std;
  
  void heapify(int arr[], int n, int i) {
    // Find largest among root, left child and right child
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
  
    if (left < n && arr[left] > arr[largest])
      largest = left;
  
    if (right < n && arr[right] > arr[largest])
      largest = right;
  
    // Swap and continue heapifying if root is not largest
    if (largest != i) {
      swap(arr[i], arr[largest]);
      heapify(arr, n, largest);
    }
  }
  
  // main function to do heap sort
  void heapSort(int arr[], int n) {
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);
  
    // Heap sort
    for (int i = n - 1; i >= 0; i--) {
      swap(arr[0], arr[i]);
  
      // Heapify root element to get highest element at root again
      heapify(arr, i, 0);
    }
  }
  
  // Print an array
  void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
      cout << arr[i] << " ";
    cout << "n";
  }
  
  // Driver code
  int main() {
    int arr[] = {1, 12, 9, 5, 6, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
  
    cout << "Sorted array is n";
    printArray(arr, n);
  }

Heap Sort Complexity

Heap Sort has O(nlog n) time complexities for all the cases ( best case, average case, and worst case).

Let us understand the reason why. The height of a complete binary tree containing n elements is log n

As we have seen earlier, to fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it.

In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps.

During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log n ~ nlog n.

During the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes log n worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is also nlog n.

Also since the build_max_heap and heap_sort steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of nlog n.

Also it performs sorting in O(1) space complexity. Compared with Quick Sort, it has a better worst case ( O(nlog n) ). Quick Sort has complexity O(n^2) for worst case. But in other cases, Quick Sort is fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.

Heap Sort Applications

Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort’s running time and constant O(1) upper bound on its auxiliary storage.

Although Heap Sort has O(n log n) time complexity even for the worst case, it doesn’t have more applications ( compared to other sorting algorithms like Quick Sort, Merge Sort ). However, its underlying data structure, heap, can be efficiently used if we want to extract the smallest (or largest) from the list of items without the overhead of keeping the remaining items in the sorted order. For e.g Priority Queues.

Similar Sorting Algorithms

1. Quicksort
2. Merge Sort

A run of heapsort sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the heap property. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration.
Class	Sorting algorithm
Data structure	Array
Worst-case performance
Best-case performance	(distinct keys) or (equal keys)
Average performance
Worst-case space complexity	total auxiliary

In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step.^[1]

Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime (and as such is used by Introsort as a fallback should it detect that quicksort is becoming degenerate). Heapsort is an in-place algorithm, but it is not a stable sort.

Heapsort was invented by J. W. J. Williams in 1964.^[2] This was also the birth of the heap, presented already by Williams as a useful data structure in its own right.^[3] In the same year, Robert W. Floyd published an improved version that could sort an array in-place, continuing his earlier research into the treesort algorithm.^[3]

Overview[edit]

The heapsort algorithm can be divided into two parts.

In the first step, a heap is built out of the data (see Binary heap § Building a heap). The heap is often placed in an array with the layout of a complete binary tree. The complete binary tree maps the binary tree structure into the array indices; each array index represents a node; the index of the node’s parent, left child branch, or right child branch are simple expressions. For a zero-based array, the root node is stored at index 0; if i is the index of the current node, then

  iParent(i)     = floor((i-1) / 2) where floor functions map a real number to the largest leading integer.
  iLeftChild(i)  = 2*i + 1
  iRightChild(i) = 2*i + 2

In the second step, a sorted array is created by repeatedly removing the largest element from the heap (the root of the heap), and inserting it into the array. The heap is updated after each removal to maintain the heap property. Once all objects have been removed from the heap, the result is a sorted array.

Heapsort can be performed in place. The array can be split into two parts, the sorted array and the heap. The storage of heaps as arrays is diagrammed here. The heap’s invariant is preserved after each extraction, so the only cost is that of extraction.

Algorithm[edit]

The heapsort algorithm involves preparing the list by first turning it into a max heap. The algorithm then repeatedly swaps the first value of the list with the last value, decreasing the range of values considered in the heap operation by one, and sifting the new first value into its position in the heap. This repeats until the range of considered values is one value in length.

The steps are:

1. Call the buildMaxHeap() function on the list. Also referred to as heapify(), this builds a heap from a list in operations.
2. Swap the first element of the list with the final element. Decrease the considered range of the list by one.
3. Call the siftDown() function on the list to sift the new first element to its appropriate index in the heap.
4. Go to step (2) unless the considered range of the list is one element.

The buildMaxHeap() operation is run once, and is O(n) in performance. The siftDown() function is O(log n), and is called n times. Therefore, the performance of this algorithm is O(n + n log n) = O(n log n).

Pseudocode[edit]

The following is a simple way to implement the algorithm in pseudocode. Arrays are zero-based and swap is used to exchange two elements of the array. Movement ‘down’ means from the root towards the leaves, or from lower indices to higher. Note that during the sort, the largest element is at the root of the heap at a[0], while at the end of the sort, the largest element is in a[end].

procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (the heap size is reduced by one)
        end ← end - 1
        (the swap ruined the heap property, so restore it)
        siftDown(a, 0, end)

The sorting routine uses two subroutines, heapify and siftDown. The former is the common in-place heap construction routine, while the latter is a common subroutine for implementing heapify.

(Put elements of 'a' in heap order, in-place)
procedure heapify(a, count) is
    (start is assigned the index in 'a' of the last parent node)
    (the last element in a 0-based array is at index count-1; find the parent of that element)
    start ← iParent(count-1)
    
    while start ≥ 0 do
        (sift down the node at index 'start' to the proper place such that all nodes below
         the start index are in heap order)
        siftDown(a, start, count - 1)
        (go to the next parent node)
        start ← start - 1
    (after sifting down the root all nodes/elements are in heap order)

(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)
procedure siftDown(a, start, end) is
    root ← start

    while iLeftChild(root) ≤ end do    (While the root has at least one child)
        child ← iLeftChild(root)   (Left child of root)
        swap ← root                (Keeps track of child to swap with)

        if a[swap] < a[child] then
            swap ← child
        (If there is a right child and that child is greater)
        if child+1 ≤ end and a[swap] < a[child+1] then
            swap ← child + 1
        if swap = root then
            (The root holds the largest element. Since we assume the heaps rooted at the
             children are valid, this means that we are done.)
            return
        else
            Swap(a[root], a[swap])
            root ← swap          (repeat to continue sifting down the child now)

The heapify procedure can be thought of as building a heap from the bottom up by successively sifting downward to establish the heap property. An alternative version (shown below) that builds the heap top-down and sifts upward may be simpler to understand. This siftUp version can be visualized as starting with an empty heap and successively inserting elements, whereas the siftDown version given above treats the entire input array as a full but «broken» heap and «repairs» it starting from the last non-trivial sub-heap (that is, the last parent node).

Also, the siftDown version of heapify has O(n) time complexity, while the siftUp version given below has O(n log n) time complexity due to its equivalence with inserting each element, one at a time, into an empty heap.^[4]
This may seem counter-intuitive since, at a glance, it is apparent that the former only makes half as many calls to its logarithmic-time sifting function as the latter; i.e., they seem to differ only by a constant factor, which never affects asymptotic analysis.

To grasp the intuition behind this difference in complexity, note that the number of swaps that may occur during any one siftUp call increases with the depth of the node on which the call is made. The crux is that there are many (exponentially many) more «deep» nodes than there are «shallow» nodes in a heap, so that siftUp may have its full logarithmic running-time on the approximately linear number of calls made on the nodes at or near the «bottom» of the heap. On the other hand, the number of swaps that may occur during any one siftDown call decreases as the depth of the node on which the call is made increases. Thus, when the siftDown heapify begins and is calling siftDown on the bottom and most numerous node-layers, each sifting call will incur, at most, a number of swaps equal to the «height» (from the bottom of the heap) of the node on which the sifting call is made. In other words, about half the calls to siftDown will have at most only one swap, then about a quarter of the calls will have at most two swaps, etc.

The heapsort algorithm itself has O(n log n) time complexity using either version of heapify.

 procedure heapify(a,count) is
     (end is assigned the index of the first (left) child of the root)
     end := 1
     
     while end < count
         (sift up the node at index end to the proper place such that all nodes above
          the end index are in heap order)
         siftUp(a, 0, end)
         end := end + 1
     (after sifting up the last node all nodes are in heap order)
 
 procedure siftUp(a, start, end) is
     input:  start represents the limit of how far up the heap to sift.
                   end is the node to sift up.
     child := end 
     while child > start
         parent := iParent(child)
         if a[parent] < a[child] then (out of max-heap order)
             swap(a[parent], a[child])
             child := parent (repeat to continue sifting up the parent now)
         else
             return

Note that unlike siftDown approach where, after each swap, you need to call only the siftDown subroutine to fix the broken heap; the siftUp subroutine alone cannot fix the broken heap. The heap needs to be built every time after a swap by calling the heapify procedure since «siftUp» assumes that the element getting swapped ends up in its final place, as opposed to «siftDown» allows for continuous adjustments of items lower in the heap until the invariant is satisfied. The adjusted pseudocode for using siftUp approach is given below.

 procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (rebuild the heap using siftUp after the swap ruins the heap property)
        heapify(a, end)
        (reduce the heap size by one)
        end ← end - 1

Variations[edit]

Floyd’s heap construction[edit]

The most important variation to the basic algorithm, which is included in all practical implementations, is a heap-construction algorithm by Floyd which runs in O(n) time and uses siftdown rather than siftup, avoiding the need to implement siftup at all.

Rather than starting with a trivial heap and repeatedly adding leaves, Floyd’s algorithm starts with the leaves, observing that they are trivial but valid heaps by themselves, and then adds parents. Starting with element n/2 and working backwards, each internal node is made the root of a valid heap by sifting down. The last step is sifting down the first element, after which the entire array obeys the heap property.

The worst-case number of comparisons during the Floyd’s heap-construction phase of heapsort is known to be equal to 2n − 2s₂(n) − e₂(n), where s₂(n) is the number of 1 bits in the binary representation of n and e₂(n) is number of trailing 0 bits.^[5]

The standard implementation of Floyd’s heap-construction algorithm causes a large number of cache misses once the size of the data exceeds that of the CPU cache.^[6]: 87 Much better performance on large data sets can be obtained by merging in depth-first order, combining subheaps as soon as possible, rather than combining all subheaps on one level before proceeding to the one above.^[7][8]

Bottom-up heapsort[edit]

Bottom-up heapsort is a variant which reduces the number of comparisons required by a significant factor. While ordinary heapsort requires 2n log₂ n + O(n) comparisons worst-case and on average,^[9] the bottom-up variant requires n log₂n + O(1) comparisons on average,^[9] and 1.5n log₂n + O(n) in the worst case.^[10]

If comparisons are cheap (e.g. integer keys) then the difference is unimportant,^[11] as top-down heapsort compares values that have already been loaded from memory. If, however, comparisons require a function call or other complex logic, then bottom-up heapsort is advantageous.

This is accomplished by improving the siftDown procedure. The change improves the linear-time heap-building phase somewhat,^[12] but is more significant in the second phase. Like ordinary heapsort, each iteration of the second phase extracts the top of the heap, a[0], and fills the gap it leaves with a[end], then sifts this latter element down the heap. But this element comes from the lowest level of the heap, meaning it is one of the smallest elements in the heap, so the sift-down will likely take many steps to move it back down.^[13] In ordinary heapsort, each step of the sift-down requires two comparisons, to find the minimum of three elements: the new node and its two children.

Bottom-up heapsort instead finds the path of largest children to the leaf level of the tree (as if it were inserting −∞) using only one comparison per level. Put another way, it finds a leaf which has the property that it and all of its ancestors are greater than or equal to their siblings. (In the absence of equal keys, this leaf is unique.) Then, from this leaf, it searches upward (using one comparison per level) for the correct position in that path to insert a[end]. This is the same location as ordinary heapsort finds, and requires the same number of exchanges to perform the insert, but fewer comparisons are required to find that location.^[10]

Because it goes all the way to the bottom and then comes back up, it is called heapsort with bounce by some authors.^[14]

function leafSearch(a, i, end) is
    j ← i
    while iRightChild(j) ≤ end do
        (Determine which of j's two children is the greater)
        if a[iRightChild(j)] > a[iLeftChild(j)] then
            j ← iRightChild(j)
        else
            j ← iLeftChild(j)
    (At the last level, there might be only one child)
    if iLeftChild(j) ≤ end then
        j ← iLeftChild(j)
    return j

The return value of the leafSearch is used in the modified siftDown routine:^[10]

procedure siftDown(a, i, end) is
    j ← leafSearch(a, i, end)
    while a[i] > a[j] do
        j ← iParent(j)
    x ← a[j]
    a[j] ← a[i]
    while j > i do
        swap x, a[iParent(j)]
        j ← iParent(j)

Bottom-up heapsort was announced as beating quicksort (with median-of-three pivot selection) on arrays of size ≥16000.^[9]

A 2008 re-evaluation of this algorithm showed it to be no faster than ordinary heapsort for integer keys, presumably because modern branch prediction nullifies the cost of the predictable comparisons which bottom-up heapsort manages to avoid.^[11]

A further refinement does a binary search in the path to the selected leaf, and sorts in a worst case of (n+1)(log₂(n+1) + log₂ log₂(n+1) + 1.82) + O(log₂n) comparisons, approaching the information-theoretic lower bound of n log₂n − 1.4427n comparisons.^[15]

A variant which uses two extra bits per internal node (n−1 bits total for an n-element heap) to cache information about which child is greater (two bits are required to store three cases: left, right, and unknown)^[12] uses less than n log₂n + 1.1n compares.^[16]

Other variations[edit]

• Ternary heapsort uses a ternary heap instead of a binary heap; that is, each element in the heap has three children. It is more complicated to program, but does a constant number of times fewer swap and comparison operations. This is because each sift-down step in a ternary heap requires three comparisons and one swap, whereas in a binary heap two comparisons and one swap are required. Two levels in a ternary heap cover 3² = 9 elements, doing more work with the same number of comparisons as three levels in the binary heap, which only cover 2³ = 8.^{[citation needed]} This is primarily of academic interest, or as a student exercise,^[17] as the additional complexity is not worth the minor savings, and bottom-up heapsort beats both.
• Memory-optimized heapsort^[6]: 87 improves heapsort’s locality of reference by increasing the number of children even more. This increases the number of comparisons, but because all children are stored consecutively in memory, reduces the number of cache lines accessed during heap traversal, a net performance improvement.
• Out-of-place heapsort^[18][19][13] improves on bottom-up heapsort by eliminating the worst case, guaranteeing n log₂n + O(n) comparisons. When the maximum is taken, rather than fill the vacated space with an unsorted data value, fill it with a −∞ sentinel value, which never «bounces» back up. It turns out that this can be used as a primitive in an in-place (and non-recursive) «QuickHeapsort» algorithm.^[20] First, you perform a quicksort-like partitioning pass, but reversing the order of the partitioned data in the array. Suppose (without loss of generality) that the smaller partition is the one greater than the pivot, which should go at the end of the array, but our reversed partitioning step places it at the beginning. Form a heap out of the smaller partition and do out-of-place heapsort on it, exchanging the extracted maxima with values from the end of the array. These are less than the pivot, meaning less than any value in the heap, so serve as −∞ sentinel values. Once the heapsort is complete (and the pivot moved to just before the now-sorted end of the array), the order of the partitions has been reversed, and the larger partition at the beginning of the array may be sorted in the same way. (Because there is no non-tail recursion, this also eliminates quicksort’s O(log n) stack usage.)
• The smoothsort algorithm^[21] is a variation of heapsort developed by Edsger W. Dijkstra in 1981. Like heapsort, smoothsort’s upper bound is O(n log n). The advantage of smoothsort is that it comes closer to O(n) time if the input is already sorted to some degree, whereas heapsort averages O(n log n) regardless of the initial sorted state. Due to its complexity, smoothsort is rarely used.^{[citation needed]}
• Levcopoulos and Petersson^[22] describe a variation of heapsort based on a heap of Cartesian trees. First, a Cartesian tree is built from the input in O(n) time, and its root is placed in a 1-element binary heap. Then we repeatedly extract the minimum from the binary heap, output the tree’s root element, and add its left and right children (if any) which are themselves Cartesian trees, to the binary heap.^[23] As they show, if the input is already nearly sorted, the Cartesian trees will be very unbalanced, with few nodes having left and right children, resulting in the binary heap remaining small, and allowing the algorithm to sort more quickly than O(n log n) for inputs that are already nearly sorted.
• Several variants such as weak heapsort require n log₂ n+O(1) comparisons in the worst case, close to the theoretical minimum, using one extra bit of state per node. While this extra bit makes the algorithms not truly in-place, if space for it can be found inside the element, these algorithms are simple and efficient,^[7]: 40 but still slower than binary heaps if key comparisons are cheap enough (e.g. integer keys) that a constant factor does not matter.^[24]
• Katajainen’s «ultimate heapsort» requires no extra storage, performs n log₂ n+O(1) comparisons, and a similar number of element moves.^[25] It is, however, even more complex and not justified unless comparisons are very expensive.

Comparison with other sorts[edit]

Heapsort primarily competes with quicksort, another very efficient general purpose in-place comparison-based sort algorithm.

Heapsort’s primary advantages are its simple, non-recursive code, minimal auxiliary storage requirement, and reliably good performance: its best and worst cases are within a small constant factor of each other, and of the theoretical lower bound on comparison sorts. While it cannot do better than O(n log n) for pre-sorted inputs, it does not suffer from quicksort’s O(n²) worst case, either. (The latter can be avoided with careful implementation, but that makes quicksort far more complex, and one of the most popular solutions, introsort, uses heapsort for the purpose.)

Its primary disadvantages are its poor locality of reference and its inherently serial nature; the accesses to the implicit tree are widely scattered and mostly random, and there is no straightforward way to convert it to a parallel algorithm.

This makes it popular in embedded systems, real-time computing, and systems concerned with maliciously chosen inputs,^[26] such as the Linux kernel.^[27] It is also a good choice for any application which does not expect to be bottlenecked on sorting.

A well-implemented quicksort is usually 2–3 times faster than heapsort.^[6][28] Although quicksort requires fewer comparisons, this is a minor factor. (Results claiming twice as many comparisons are measuring the top-down version; see § Bottom-up heapsort.) The main advantage of quicksort is its much better locality of reference: partitioning is a linear scan with good spatial locality, and the recursive subdivision has good temporal locality. With additional effort, quicksort can also be implemented in mostly branch-free code, and multiple CPUs can be used to sort subpartitions in parallel. Thus, quicksort is preferred when the additional performance justifies the implementation effort.

The other major O(n log n) sorting algorithm is merge sort, but that rarely competes directly with heapsort because it is not in-place. Merge sort’s requirement for Ω(n) extra space (roughly half the size of the input) is usually prohibitive except in the situations where merge sort has a clear advantage:

• When a stable sort is required
• When taking advantage of (partially) pre-sorted input
• Sorting linked lists (in which case merge sort requires minimal extra space)
• Parallel sorting; merge sort parallelizes even better than quicksort and can easily achieve close to linear speedup
• External sorting; merge sort has excellent locality of reference

Example[edit]

Let { 6, 5, 3, 1, 8, 7, 2, 4 } be the list that we want to sort from the smallest to the largest. (NOTE, for ‘Building the Heap’ step: Larger nodes don’t stay below smaller node parents. They are swapped with parents, and then recursively checked if another swap is needed, to keep larger numbers above smaller numbers on the heap binary tree.)

Build the heap[edit]

Sorting[edit]

Notes[edit]

References[edit]

• Williams, J. W. J. (1964). «Algorithm 232 – Heapsort». Communications of the ACM. 7 (6): 347–348. doi:10.1145/512274.512284.
• Floyd, Robert W. (1964). «Algorithm 245 – Treesort 3». Communications of the ACM. 7 (12): 701. doi:10.1145/355588.365103. S2CID 52864987.
• Carlsson, Svante [in Swedish] (1987). «Average-case results on heapsort». BIT Numerical Mathematics. 27 (1): 2–17. doi:10.1007/bf01937350. S2CID 31450060.
• Knuth, Donald (1997). «§5.2.3, Sorting by Selection». The Art of Computer Programming. Vol. 3: Sorting and Searching (3rd ed.). Addison-Wesley. pp. 144–155. ISBN 978-0-201-89685-5.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7. Chapters 6 and 7 Respectively: Heapsort and Priority Queues
• A PDF of Dijkstra’s original paper on Smoothsort
• Heaps and Heapsort Tutorial by David Carlson, St. Vincent College

External links[edit]

• Animated Sorting Algorithms: Heap Sort at the Wayback Machine (archived 6 March 2015) – graphical demonstration
• Courseware on Heapsort from Univ. Oldenburg – With text, animations and interactive exercises
• NIST’s Dictionary of Algorithms and Data Structures: Heapsort
• Heapsort implemented in 12 languages
• Sorting revisited by Paul Hsieh
• A PowerPoint presentation demonstrating how Heap sort works that is for educators.
• Open Data Structures – Section 11.1.3 – Heap-Sort, Pat Morin