Изменения

Перейти к: навигация, поиск

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

54 байта добавлено, 12:36, 21 марта 2015
Реализация
== Реализация ==
<tex>A</tex> {{---}} массив, который необходимо отсортировать; <tex>n</tex> {{---}} количество элементов в нем; <tex>build\_heapmathrm{buildHeap(A)} </tex> - процедура, которая строит из передаваемого массива невозрастающую кучу в этом же массиве; <tex>sift\_downmathrm{siftDown(A, i, len)} </tex> {{---}} процедура, которая просеивает вниз элемент <tex>A[i]</tex> в куче из <tex>len</tex> элементов, находящихся в начале массива <tex>A</tex>.<pre> '''fun''' heapsort(A: '''list <T>''') build_heap buildHeap(A); heap_size heapSize = A.size; '''for ''' i = 0 '''to ''' n - 2 swap(A[0], A[n - 1 - i]); heap_size heapSize--; sift_down siftDown(A, 0, heap_size);</pre>
== Сложность ==
107
правок

Навигация