Pseudokod

Lekcja 4 z 9 w kursie Sortowanie przez kopcowanie — seria DSA w Coddy.

siftDown(array, i, size):
   loop:
      largest = i
      left = 2*i + 1
      right = 2*i + 2
      if left < size and array[left] > array[largest]:  largest = left
      if right < size and array[right] > array[largest]: largest = right
      if largest == i: stop
      swap array[i] and array[largest]
      i = largest

heapSort(array):
   n = length(array)
   for i from n/2 - 1 down to 0:   # build max-heap
      siftDown(array, i, n)
   for end from n-1 down to 1:     # extract max repeatedly
      swap array[0] and array[end]
      siftDown(array, 0, end)

siftDown przesuwa zbyt małego rodzica w dół, za jego większe dziecko, aż zostanie przywrócona własność kopca maksymalnego. size określa, jaka część tablicy nadal należy do kopca.
Faza budowania: przesunięcie w dół każdego węzła niebędącego liściem (od ostatniego rodzica, o indeksie n/2 - 1, aż do korzenia) zamienia dowolną tablicę w kopiec maksymalny.
Faza sortowania: w każdym kroku bieżące maksimum jest przenoszone na koniec, a kopiec zmniejszany, dzięki czemu tablica zapełnia się posortowanymi elementami od tyłu.

Spróbuj swoich sił

Ta lekcja nie zawiera wyzwania z kodem.