Пирамидальная сортировка на C++

#алгоритм #сортировка #cpp

Приведите пример пирамидальной сортировки (сортировки кучи) на C++.    

Ответы

Ответ 1

Сортировка "кучи" на C++.
#include 

template 
inline void swap( T & arg1, T & arg2)
{
    T temp = arg1;
    arg1 = arg2;
    arg2 = temp;
};
template 
void shiftup(T * a, int size, int indexToShift) {
    int i = indexToShift;
    while(i > 1) {
        if(a[i] < a[i/2]) {
            swap(a[i], a[i/2]);
            i /= 2;
        } else
            break;
    }
}

template 
void shiftdown(T * a, int size, int indexToShift) {
    int i = indexToShift;
    int min;
    while ( i < size) {
        if ( i*2 <= size) {
            if (i*2+1 <= size) {
                min = a[i*2] < a[i*2+1] ? i*2 : i*2+1;
            } else 
                min = i*2;
            if (a[i] > a[min]) {
                swap(a[i], a[min]);
                i = min;
            } else
                break;
        } else 
            break;
    }
}

template  
void heap_sort( T * a, int size) {
    for (int i = 1; i < size; ++i) 
        shiftup(a, size, i);
    for (int i = size-1; i > 1; i--) {
        swap(a[1], a[i]);
        shiftdown(a, i-1, 1);
    }
}


Ответ 2

В С++ уже есть функции для работы с кучей - std::make_heap и std::sort_heap, по этому
сортировка кучей реализуется тривиально:

template>
void heap_sort(RandomAccessIter first, RandomAccessIter last, Compare cmp = Compare{}) {
    std::make_heap(first, last, cmp);
    std::sort_heap(first, last, cmp);
}