Pseudocodice

Lezione 4 di 9 del corso Heap Sort - Serie DSA di 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 spinge verso il basso un genitore troppo piccolo, oltre il figlio più grande, finché la proprietà di max-heap non viene ripristinata. size indica quanta parte dell’array fa ancora parte dell’heap.
Fase di costruzione: spostare verso il basso ogni nodo non foglia (dall’ultimo genitore, all’indice n/2 - 1, fino alla radice) trasforma qualsiasi array in un max-heap.
Fase di ordinamento: a ogni passaggio il massimo corrente viene spostato in fondo e l’heap si riduce, quindi l’array si riempie ordinato a partire dalla fine.

Provalo tu

Questa lezione non include una sfida di codice.