Раздел «Алгоритмы».HeapSort:

Сортировка методом двоичной кучи

Это сортировка интересна по двум причинам:

Алгоритм сортировки

Добавим N чисел в двоичную кучу (используя их самих в качестве ключа), затем выполним функцию ExtractMin N раз, то есть извлечем элементы из двоичной кучи в порядке возрастания.

1:h = new Heap
2:foreach a do
3:    h->Insert(a);
4:while( h is not empty )
5:    print h->ExtractMin()

для тех, кто пишет на C++ естественнее писать так:

h = new Heap();
while(scanf("%d", &a)==1)
   h->Insert(a);
while( h->ExtractMin(&a) )
   printf("%d ", a);

Операции Insert и ExtractMin каждая выполняются по N раз.

Замечания

-- ArtemVoroztsov - 02 Nov 2004

AlgorithmClasifyForm
Type: Теория
Scope: Структуры данных
Strategy:  
Complexity: Low