Пирамидальная сортировка (Heapsort) + Реализация на С++

Сортировка основана на применении структуры данных - пирамида (сортирующего дерева, кучи). Пирамида - двоичное дерево, для которого выполняются условия:

1. Значение в любой вершине не меньше, чем значения её потомков.
2. Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.
3. Последний слой заполняется слева направо

Пример представления массива в виде пирамиды:

Для организации такой кучи мы будем использовать одномерный массив. Для того, чтобы свойства кучи выполнялись, нужна функция, к-ая Max_Heapify(A,i), где i - индекс массива. Она опускает значение элемента A[i] вниз по пирамиде, до тех пор, пока поддерево с корнем отвечающим элементу A[i] не становится невозрастающей пирамидой, то есть все элементы ОТСОРТИРОВАНЫ. (или по другому бинарное дерево сбалансировано)

Пример работы Max_Heapify можно почитать на вики : Max_Heapify Example

Для доступа к родительскому элементу правому и левому дочерним элементам реализуем встраиваемые функции:

inline unsigned Parent(unsigned i) {
 return floor((double)(i/2));
}

inline unsigned Left(unsigned i) {
 return ((2*i)+1);
}

inline unsigned Right(unsigned i) {
 return ((2*i)+2);
}

Реализуем функцию проталкивания меньшего элемента вниз пирамиды.
Пример проталкивания:

template < typename Type>
void Max_Heapify(Type mas[], unsigned index, unsigned heap_size){
 unsigned l=Left(index); //индекс лев. дочернего эл-та
 unsigned r=Right(index);  //индекс прав. дочернего эл-та

 unsigned largest; //хранит индекс большего эл-та
 if ((l< heap_size l="l" mas="mas">mas[index])) { //проверка, что левый элемент больше
  largest=l; //левый дочерний элемент больший элемент
 }
 else 
  largest=index; //mas[index] - больший элемент
 if ((r< heap_size mas="mas" r="r">mas[largest]))
  largest=r;
 if (largest!=index){ //если есть из дочерних элементов большие
  swap(mas[index],mas[largest]); //обменяемся с большим
  Max_Heapify(mas,largest, heap_size); //вызовем рекурсивно опять для того же элемента
 }
}

Для построения пирамиды из массива реализуем процедуру Build_Max_Heap
template < typename Type>
void Build_Max_Heap (Type mas[], unsigned heap_size){
 for (unsigned index=Parent(heap_size-1); index>0; index--){
  Max_Heapify(mas, index, heap_size);
 }
}

Теперь реализуем саму сортировку. Сначала строим пирамиду, потом будем удалять элементы из корня пирамиды и перестраивать дерево.

template < typename Type>
void Heapsort(Type mas[], unsigned mas_size){
 unsigned heap_size=mas_size;
 Build_Max_Heap(mas,heap_size);
 for (unsigned index=mas_size-1; index>=1; index--){
  swap(mas[0],mas[index]);
  heap_size--;
  Max_Heapify(mas,0, heap_size);
 }
}

Пирамидальная сортировка для ленивых :D

template < typename Iterator>
void heapsort(Iterator begin, Iterator end)
{
    std::make_heap(begin, end);
    std::sort_heap(begin, end);
}
int main {
    double valsToSort[] = {9,4,2,1,5,6};
    const int VSIZE = sizeof(valsToSort)/sizeof(*valsToSort);
    heapsort(valsToSort, valsToSort+VSIZE); 
}

Posted in: Алгоритмы, Сортировки, CPP