Heapsort è un algoritmo di ordinamento che ha una complessità temporale di O (nlogn) ed esegue l'ordinamento utilizzando la complessità di spazio O (1). Tuttavia, so che poiché è instabile, non trova molte applicazioni (ad esempio rispetto ad altri algoritmi di ordinamento).
So che è usato per la programmazione a intervalli.
Quali sono alcune applicazioni pratiche di heapsort?
EDIT: come indicato da @AProgrammer, l'ordinamento rapido non è stabile neanche.
Heapsort è ottimo quando devi conoscere solo il "più piccolo" (o "il più grande") di una raccolta di elementi, senza il sovraccarico di mantenere gli articoli rimanenti in ordine. Ad esempio, un PriorityQueue.
Quicksort non è stabile. Quicksort ha un fattore costante inferiore rispetto all'ordinamento heap, ma la complessità peggiore è O (N ^ 2), quindi alcune varianti tornano a heapsort per evitare tale comportamento (ad esempio introsort , ma sono abbastanza sicuro di aver visto l'idea applicata nei primi anni '90).
L'ordinamento heap è sempre O (nlogn) senza il caso peggiore Quicksort di O (n 2 ). Questo è importante per mettere un limite superiore al tempo di elaborazione massimo.
Heapsort è anche utile in alcune applicazioni perché l'elaborazione può iniziare prima che tutti i dati siano disponibili. I dati potrebbero essere ricevuti in pacchetti con ritardi. Anziché attendere l'arrivo di tutti i dati prima di iniziare a ordinare, Heapsort può iniziare con il primo elemento ad arrivare e procedere in modo incrementale in modo che sia quasi completo quando l'ultimo elemento è disponibile.
Quicksort non si comporta bene su piccoli input, perché c'è una grande possibilità che il pivot venga scelto male (non una mediana di tutti gli elementi ordinati). Quindi, Heapsort o anche Insertion sort viene in genere utilizzato per array di dimensioni.
Da qui deriva un'altra applicazione di heapsort - Intosort . Introsort è un algoritmo di ordinamento, che combina punti di forza sia di quicksort che di heapsort. I grandi array vengono ordinati usando quicksort, ma quando viene raggiunto il limite di profondità previsto - log2n - l'algoritmo passa a heapsort.
Direi che se la complessità O (n log2n) non è necessaria per essere garantita, che quicksort è (quasi) sempre usato, perché è in media più veloce ed è un algoritmo di libreria ampiamente utilizzato. Se vuoi migliorare il comportamento di Quicksort, lo usi in combinazione con Heapsort. E solo quando si deve garantire O (n log2n), le implementazioni usano semplicemente heapsort.
Leggi altre domande sui tag algorithms sorting use-case heap