Сортировка основана на применении структуры данных - пирамида (сортирующего дерева, кучи). Пирамида - двоичное дерево, для которого выполняются условия:
Для доступа к родительскому элементу правому и левому дочерним элементам реализуем встраиваемые функции:
- Значение в любой вершине не меньше, чем значения её потомков.
- Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.
- Последний слой заполняется слева направо
Пример представления массива в виде пирамиды:
Для организации такой кучи мы будем использовать одномерный массив. Для того, чтобы свойства кучи выполнялись, нужна функция, к-ая 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);
}
}
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);
}
