Confronti
Scambi
Estratti

  • In discesa
  • Confrontate
  • Scambiate
  • Al loro posto

Scopri di più sull'heap sort

Heap sort

L'heap sort legge la lista come un albero binario e la riorganizza in un max-heap, in cui ogni genitore è grande almeno quanto i suoi figli. Il valore più grande è allora in cima. Scambialo con la fine, dove resta, ripara l'heap e ripeti. L'app disegna l'heap come un albero sopra le barre, così puoi seguire ogni valore mentre scende. Premi Avvia per guardare l'ordinamento, oppure Passo e Indietro per procedere un confronto alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto. L'albero sopra le barre mostra gli stessi valori come heap. I riquadri contano confronti, scambi e valori estratti dall'heap. Scegli quante barre usare, come partono, oppure inserisci i tuoi numeri. Con l'area selezionata, i tasti freccia avanzano di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.

Come funziona

  1. Scegli quante barre usare e come partono: casuali, quasi ordinate, in ordine inverso o con pochi valori distinti. Oppure inserisci i tuoi numeri.
  2. Premi Avvia, oppure usa Passo e Indietro per procedere un confronto alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto dell'ordinamento.
  3. Osserva l'albero: prima ogni genitore scende finché l'heap è costruito, poi la radice viene scambiata con la fine e l'heap si accorcia di uno.

Come funziona l'heap sort

Leggi la lista come un albero: il valore in posizione i ha i figli nelle posizioni 2i + 1 e 2i + 2. Costruisci un max-heap facendo scendere ogni genitore, a partire dall'ultimo: finché un valore è più piccolo del suo figlio più grande, i due si scambiano. Quando la radice contiene il valore più grande, scambialo con l'ultimo valore dell'heap. Quel valore è ora definitivo, l'heap è più corto di uno e la nuova radice scende per renderlo di nuovo un heap. Ripeti finché l'heap è vuoto.

Sempre n log n, in loco

L'albero ha circa log₂ n livelli, quindi ogni discesa richiede al massimo circa 2 log₂ n confronti, e la costruzione dell'heap meno di 2n. Così l'heap sort ha un caso peggiore di circa 2n log₂ n confronti, senza buffer: per 40 valori, al massimo 352. A differenza del quicksort non ha input sfavorevoli, e a differenza del merge sort non richiede memoria aggiuntiva. In pratica di solito è più lento di entrambi, perché salta qua e là nella lista, e non è stabile.

Domande frequenti

Come funziona l'heap sort?

Trasforma la lista in un max-heap, un albero memorizzato nella lista in cui ogni genitore è grande almeno quanto i suoi figli. Poi scambia più volte il valore più grande, nella radice, con la fine dell'heap e fa scendere la nuova radice per riparare l'heap.

Cos'è un heap?

Un albero binario completo memorizzato in una lista senza puntatori: i figli della posizione i sono le posizioni 2i + 1 e 2i + 2. In un max-heap ogni genitore è grande almeno quanto i suoi figli, quindi il valore più grande è sempre nella radice, in posizione 0.

Perché costruire l'heap è veloce?

La maggior parte dei valori sta vicino al fondo dell'albero e può scendere solo di uno o due livelli. Sommando il lavoro su tutti i livelli si ottengono meno di 2n confronti per l'intera costruzione, non n log n.

L'heap sort è stabile?

No. Scambiare la radice con la fine sposta i valori su lunghe distanze, quindi valori uguali possono cambiare ordine.

I miei numeri vengono inviati da qualche parte?

No. L'ordinamento avviene nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor