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

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

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

1
2
3
4
5
6
7
void heap_make(int n)
{
    for (int i = 1; i <= n; ++i)
    {
    heap_push(i);
    }
}

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

1
2
3
4
5
6
7
void heap_make(int n)
{
    for (int i = n - 1; i >= 0; i--)
    {
        heapify(i, n);
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 принимает на вход номер элемента в массиве, который необходимо добавить в кучу.

1
2
3
4
5
6
7
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;
    }
}

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

1
2
3
4
5
6
7
8
9
10
void heap_sort(int n)
{
    heap_make(n);
    while(n>0)
    {
        swap(arr[0],arr[n-1]);
        n--;
        heapify(0,n);
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <algorithm>
#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]<<endl;
    }
    return 0;
}

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

    В начале статьи, по всей видимости, ошибка.
    Перепутаны описания функций и код. Медленный работает за 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++