Сортировка кучей (Heap Sort) (реализация на C++)

C++   13 марта 2012  Автор статьи:  

Сортировку кучей называют также пирамидальной сортировкой. Сущетсвуют два способа построения кучи: быстрый и медленный. Для этого реализуем функцию heap_make(int n), где n — количество элементов в массиве, который мы хотим сделать кучей.
Рассмотрим оба варианта построения кучи:
1) Медленный работает за O(n\times\log{n}) и основан на вызове функции heapify

void heap_make(int n)
{
for (int i = 1; i <= n; ++i) { heap_push(i); } }

2) Быстрый работает за линию O(n\times\log{n})

void heap_make(int n)
{
for (int i = n - 1; i >= 0; i--)
{
heapify(i, n);
}
}

Более подробно о функциях heapify и heapsort вы можете прочитать в статье Куча. Приведем пример реализации данных функций:
1)heapify принимает на вход позицию корня кучи в массиве и количество элементов в массиве

void heapify (int pos, int n) {
while (2 * pos + 1 < n) { //пока не вышли за грань массива int t = 2 * pos +1;// находим первого сына if (2 * pos + 2 < n && arr[2 * pos + 2] >= arr[t])
//если второй сын существует и больше чем первый
{
t = 2 * pos + 2;//берем его
}
if (arr[pos] < arr[t]) { // если наибольший из сыновей больше // чем предок, то меняем их местами swap(arr[pos], arr[t]); pos = t;// теперь предком является следующий элемент } else break; //иначе куча с головой в pos построена. } }

2)Heap_Push принимает на вход номер элемента в массиве, который необходимо добавить в кучу.

void heap_push(int v) {
int t = v - 1;
while (t > 0 && arr[(t - 1) / 2] < arr[t]) { swap(arr[(t - 1) / 2], arr[t]); t = (t - 1) / 2; } }

И наконец, чтобы отсортировать массив, т.е из кучи получить массив необходимо выполнить следующую функцию:

void heap_sort(int n)
{
heap_make(n);
while(n>0)
{
swap(arr[0],arr[n-1]);
n--;
heapify(0,n);
}
}


Массив arr является глобальным для всей программы. Ниже приведу весь код необходимый для сортировки кучей.
Код пирамидальной сортировки:

#include
#include
#define NMAX 50001
using namespace std;
int arr[NMAX+1];

void heapify (int pos, int n) {
while (2 * pos + 1 < n) { int t = 2 * pos +1; if (2 * pos + 2 < n && arr[2 * pos + 2] >= arr[t])
{
t = 2 * pos + 2;
}
if (arr[pos] < arr[t]) { swap(arr[pos], arr[t]); pos = t; } else break; } } void heap_make(int n) { for (int i = n - 1; i >= 0; i--)
{
heapify(i, n);
}
}
void heap_sort(int n)
{
heap_make(n);
while(n>0)
{
swap(arr[0],arr[n-1]);
n--;
heapify(0,n);
}
}

int main()
{

int n;
cin>>n;
for(int i = 0; i < n; i ++) { cin>> arr[i];
}
heap_sort(n);
for(int i = 0; i < n; i ++) { cout << arr[i]<

  • Сергей Егоров

    В начале статьи, по всей видимости, ошибка.
    Перепутаны описания функций и код. Медленный работает за O(n * logn), а быстрый за линию O(n).

  • DFooz

    ещё можно улучшить 2 функции

    void heapify (int pos, int n) {

    while (2 * pos + 1 < n) {

    int t = 2 * pos +1;

    if (t + 1 = arr[t])
    ++t;

    if (arr[pos] = 0; —i)

    {

    heapify(i, n);

    }

    }

Научиться программировать

  • на Delphi

  • на Java

  • на C++