Пирамидальная сортировка (Heap Sort)

[Все сортировки]

Теория: читаем дивную статью с картинками

Практика: informatics.mccme.ru

Визуализатор: rain.ifmo.ru [Java]

Реализация:
Общую логику программы можно отследить по этому фрагменту кода:

1. // просейка вверх узла с индексом pos
2. void shiftUp(vector<int> &mas, int pos)
3. {
4.   while (!isRoot(pos) && mas[pos]>mas[Parent(pos)])
5.   {
6.     swap(mas[pos],mas[Parent(pos)]);
7.     pos = Parent(pos);
8.   }
9. }
10. // просейка вниз узла с индексом pos
11. void shiftDown(vector<int> &mas, int pos, int n)
12. {
13.   while (!isList(pos,n))
14.   {
15.     int posMaxChild = Left(pos);
16.     if (isRightExist(pos,n))
17.     {
18.       if (mas[Left(pos)] < mas[Right(pos)])
19.         posMaxChild = Right(pos);
20.     }
21.     if (mas[pos]<mas[posMaxChild])
22.     {
23.       swap(mas[pos],mas[posMaxChild]);
24.       pos = posMaxChild;
25.     }
26.     else
27.       break;
28.   } 
29. }
30. // преобразовать входной массив в кучу
31. void make_heap(vector<int> &mas)
32. {
33.   for (int i=1;i<mas.size();i++)
34.     shiftUp(mas,i);
35. }
36. // упорядочивание входного массива пирамидальной сортировкой
37. void heap_sort(vector<int> &mas)
38. {
39.   make_heap(mas);
40.   int size = mas.size();
41.   for (int i=0;i<mas.size();i++)
42.   {
43.     swap(mas[0],mas[size-1]);
44.     size--;
45.     shiftDown(mas,0,size);
46.   }
47. }

* This source code was highlighted with Source Code Highlighter.

Полный исходник глядим здесь

Для учебных целей можно рассмотреть рекурсивную, более понятную запись функций shiftDown и shiftUp:

1. // просейка вверх
2. void shiftUp(vector<int> &mas, int pos)
3. {
4.   if (isRoot(pos))
5.     return;
6.   if (mas[Parent(pos)] < mas[pos])
7.   {
8.     swap(mas[Parent(pos)],mas[pos]);
9.     shiftUp(mas,Parent(pos));
10.   }
11. }
12. // просейка вниз
13. void shiftDown(vector<int> &mas, int pos, int n)
14. {
15.   if (isList(pos,n))
16.     return;
17.   int posMaxChild = Left(pos);
18.   if (isRightExist(pos,n))
19.   {
20.     if (mas[Left(pos)] < mas[Right(pos)])
21.       posMaxChild = Right(pos);
22.   }
23.   if (mas[pos]<mas[posMaxChild])
24.   {
25.     swap(mas[pos],mas[posMaxChild]);
26.     shiftDown(mas, posMaxChild,n);
27.   }
28. }

* This source code was highlighted with Source Code Highlighter.