Aggiornamento algoritmo. Perché heapsort è un algoritmo di supporto?

I mean an extra data structure populated with the elements of the array to be sorted i.e. a heap, is used to assist in the extraction of the min value and the sorting process.

No. La matrice viene trasformata per conformarsi al vincolo dell'heap senza utilizzare più di O (1) memoria aggiuntiva. (In realtà tutto ciò che serve è una memoria aggiuntiva sufficiente per contenere un elemento dell'array, per scopi di scambio, più una variabile booleana o due e una variabile ciclo o due).

Ok, da un punto di vista tecnico può essere che l'heapsort viene in genere spiegato come se utilizzasse un heap separato, ma è perfettamente possibile implementarlo sul posto.

Potresti perdere la comprensione fondamentale che un array può essere usato per specificare il layout di un albero.

Supponiamo che tu abbia un albero binario e che un nodo interno sia all'indice i dell'array. Quindi l'indice della matrice del genitore e dei figli di quel nodo può essere trovato da:

Parent(i) = floor(i/2)
Left child(i) = 2i
Right child(i) = 2i + 1

See:

link

Poiché l'heap può essere conservato e organizzato interamente in un array, quindi heapsort può essere eseguito sul posto spostando gli elementi all'interno dell'array di input. Infatti, l'heap è costruito e manipolato usando l'array di input originale.

Se, come dici tu, avevi davvero bisogno di una struttura extra per costruire l'heap, quindi heapsort NON sarebbe un algoritmo di ordinamento interno.

Tuttavia, questo non è il caso. È possibile creare l'heap sullo stesso array che si desidera ordinare, dopodiché si applica l'algoritmo di heapsort, quindi ordina inplace.

In computer science, an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.

Wikipedia - Algoritmo sul posto

È considerato valido perché i requisiti di spazio sono trascurabili (costanti o nulli se si utilizzano operazioni bit a bit per scambiare gli elementi). MergeSort, ad esempio, non è a posto perché il set di input non viene modificato in ogni iterazione dell'esempio di ricerca.

Il modo migliore per illustrare le differenze tra algoritmi sul posto e algoritmi out-of-place è probabilmente quello di guardare il seguente codice di inversione della stringa C / C ++ che lo fa in posizione (da K & R):

void reverse(char s[])
{
      int c, i, j;

      for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
         c = s[i];
         s[i] = s[j];
         s[j] = c;
      }
}

Se, ad esempio, leggevi la stringa di input dalla fine e disponevi i caratteri in un altro buffer, sarebbe un algoritmo di inversione della stringa fuori luogo.