b"\n_START_ARTICLE_\nHeapsort\n_START_SECTION_\nOperazioni sugli heap\n_START_PARAGRAPH_\nL'heap pu\xc3\xb2 essere rappresentato graficamente da un array. Dato ci\xc3\xb2 pu\xc3\xb2 essere utile conoscere come operare sull'heap in modo da conoscere il padre e i figli di un determinato elemento di indice i._NEWLINE_La funzione per calcolare l'elemento padre di i \xc3\xa8 ._NEWLINE_Per il calcolo del figlio sinistro \xc3\xa8  e per il destro \xc3\xa8 ._NEWLINE_Un MaxHeap \xc3\xa8 un heap binario se ogni elemento soddisfa la propriet\xc3\xa0 del MaxHeap: ogni elemento \xc3\xa8 minore o uguale al nodo padre._NEWLINE_Ovvero, dato un array A, un indice i e la lunghezza n del vettore, dove i rappresenta l'indice di ogni elemento:_NEWLINE_ per ogni _NEWLINE_Un MinHeap, al contrario, deve soddisfare la seguente propriet\xc3\xa0:_NEWLINE_ per ogni _NEWLINE_Determinare il massimo o il minimo elemento da una di queste due strutture \xc3\xa8 immediato, infatti il primo elemento  \xc3\xa8 sempre il massimo o il minimo dell'heap, a seconda della propriet\xc3\xa0 che si \xc3\xa8 utilizzata.\n_START_SECTION_\nHeap sort\n_START_PARAGRAPH_\nL'algoritmo che ordina in senso crescente inizia creando uno heap decrescente.  Per ogni iterazione si copia la radice (primo elemento dell'array) in fondo all'array stesso, eseguendo uno scambio di elementi.  L'algoritmo poi ricostruisce uno heap di  elementi spostando verso il basso la nuova radice, e ricomincia con un altro scambio (tra il primo elemento dell'array e quello in posizione ), eseguendo un ciclo che considera array di dimensione progressivamente decrescente._NEWLINE_Si pu\xc3\xb2 dimostrare che la complessit\xc3\xa0 asintotica massima dell'heap sort \xc3\xa8 .  Tuttavia, in generale (e soprattutto per array quasi ordinati) altri algoritmi con la medesima complessit\xc3\xa0 asintotica, per esempio quick sort o merge sort, ottengono migliori prestazioni.  Per array di piccole dimensioni \xc3\xa8 addirittura pi\xc3\xb9 veloce l'insertion sort nonostante abbia una complessit\xc3\xa0 di .\n_START_SECTION_\nVariante di Floyd\n_START_PARAGRAPH_\nNella costruzione della struttura heap mediante l'algoritmo heap sort, si confrontano il massimo dei figli portandoli alla radice: cos\xc3\xac si ha un risparmio sul numero di confronti da eseguire."