Heap sort
Ultimo aggiornamento
L'heap sort tratta l'array come un heap binario. Prima costruisce un max-heap, così l'elemento più grande sta alla radice (indice 0). Poi scambia ripetutamente la radice con l'ultimo elemento non ordinato, fissando il massimo al suo posto, e fa scendere la nuova radice (sift-down) per ripristinare la proprietà di heap. Premi play qui sopra per vedere la costruzione dell'heap e le estrazioni.
L'heap sort garantisce tempo O(n log n) come il merge sort, ma ordina in loco con solo O(1) di spazio extra. Non è stabile e tende a sfruttare la cache peggio del quicksort, quindi si sceglie spesso quando contano sia un limite garantito sia una memoria costante.
Complessità temporale e spaziale
| Caso | Complessità | Note |
|---|---|---|
| Caso migliore | O(n log n) | Costruzione + n estrazioni |
| Caso medio | O(n log n) | Ordine casuale |
| Caso peggiore | O(n log n) | Garantito |
| Spazio | O(1) | In loco |
| Stabile | No | Il sift-down riordina gli elementi uguali |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Costruisci un max-heap dall'array (sift-down a partire dall'ultimo genitore). |
| 2 | Scambia la radice (il massimo) con l'ultimo elemento dell'heap. |
| 3 | Riduci l'heap di uno: l'ultima posizione ora è ordinata. |
| 4 | Fai scendere la nuova radice per ripristinare la proprietà di max-heap. |
| 5 | Ripeti finché nell'heap resta un solo elemento. |
Esempio svolto
Ordinamento di [3, 1, 6, 5, 2, 4]. La barra | segna il confine tra l'heap che si riduce e la coda ordinata:
| Passata | Array | Azione |
|---|---|---|
| Costruzione heap | [6, 5, 4, 1, 2, 3] | Sift-down dall'ultimo genitore per costruire il max-heap; ora 6 è alla radice. |
| 1 | [5, 3, 4, 1, 2 | 6] | Scambia la radice 6 con l'ultima posizione, riduci l'heap e fai scendere 3. |
| 2 | [4, 3, 2, 1 | 5, 6] | Porta fuori la radice 5, poi fai scendere 2 così 4 sale alla radice. |
| 3 | [3, 1, 2 | 4, 5, 6] | Porta fuori la radice 4, poi fai scendere 1 così 3 sale alla radice. |
| 4 | [2, 1 | 3, 4, 5, 6] | Porta fuori la radice 3; 2 rispetta già la proprietà di heap. |
| 5 | [1 | 2, 3, 4, 5, 6] | Porta fuori la radice 2; resta un solo elemento, quindi l'array è ordinato. |
Quando usare l'heap sort
| Usalo quando | Evitalo quando |
|---|---|
Ti serve un caso peggiore O(n log n) garantito, senza rischio di O(n²). | Ti serve un ordinamento stabile che preservi l'ordine delle chiavi uguali. |
La memoria è poca: ordina in loco con solo O(1) di spazio extra. | Contano le prestazioni di cache e i dati stanno in memoria: il quicksort di solito è più veloce. |
| Stai già mantenendo un heap (ad es. una coda di priorità) sui dati. | Vuoi il minor numero di confronti: merge sort e quicksort spesso ne fanno meno in pratica. |
| Un input non fidato potrebbe innescare il caso peggiore del quicksort e non puoi randomizzare. | I dati sono quasi ordinati: l'insertion sort su di essi gira in tempo quasi lineare. |
Codice Heap Sort
Un'implementazione di Heap Sort pulita ed eseguibile in Python, JavaScript, Java, C++, C. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Heap Sort in Python
Python
1def heap_sort(a):2 n = len(a)3 # Build a max-heap, deepest parent first4 for i in range(n // 2 - 1, -1, -1):5 sift_down(a, i, n)6 # Repeatedly move the max to the end and shrink the heap7 for end in range(n - 1, 0, -1):8 a[0], a[end] = a[end], a[0]9 sift_down(a, 0, end)10 return a11
12
13def sift_down(a, i, size):14 while True:15 largest = i16 left, right = 2 * i + 1, 2 * i + 217 if left < size and a[left] > a[largest]:18 largest = left19 if right < size and a[right] > a[largest]:20 largest = right21 if largest == i:22 return23 a[i], a[largest] = a[largest], a[i]24 i = largest25
26
27nums = [12, 11, 13, 5, 6, 7]28print("Before:", nums)29heap_sort(nums)30print("After: ", nums)Codice Heap Sort in JavaScript
JavaScript
1function heapSort(a) {2 const n = a.length;3 // Build a max-heap, then repeatedly move the max to the end4 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);5 for (let end = n - 1; end > 0; end--) {6 [a[0], a[end]] = [a[end], a[0]];7 siftDown(a, 0, end);8 }9 return a;10}11
12function siftDown(a, i, size) {13 while (true) {14 const left = 2 * i + 1;15 const right = 2 * i + 2;16 let largest = i;17 if (left < size && a[left] > a[largest]) largest = left;18 if (right < size && a[right] > a[largest]) largest = right;19 if (largest === i) return;20 [a[i], a[largest]] = [a[largest], a[i]];21 i = largest;22 }23}24
25const data = [5, 2, 9, 1, 7, 3];26console.log("Before:", data);27console.log("Sorted:", heapSort([...data]));Codice Heap Sort in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void heapSort(int[] arr) {5 int n = arr.length;6 // Build a max-heap, deepest parent first7 for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);8 // Repeatedly move the max to the end and shrink the heap9 for (int end = n - 1; end > 0; end--) {10 swap(arr, 0, end);11 siftDown(arr, 0, end);12 }13 }14
15 static void siftDown(int[] arr, int i, int size) {16 while (true) {17 int largest = i, l = 2 * i + 1, r = 2 * i + 2;18 if (l < size && arr[l] > arr[largest]) largest = l;19 if (r < size && arr[r] > arr[largest]) largest = r;20 if (largest == i) return;21 swap(arr, i, largest);22 i = largest;23 }24 }25
26 static void swap(int[] arr, int a, int b) {27 int tmp = arr[a];28 arr[a] = arr[b];29 arr[b] = tmp;30 }31
32 public static void main(String[] args) {33 int[] arr = {12, 11, 13, 5, 6, 7};34 System.out.println("Before: " + Arrays.toString(arr));35 heapSort(arr);36 System.out.println("After: " + Arrays.toString(arr));37 }38}Codice Heap Sort in C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void siftDown(std::vector<int>& a, int n, int i) {11 while (true) {12 int largest = i, l = 2 * i + 1, r = 2 * i + 2;13 if (l < n && a[l] > a[largest]) largest = l;14 if (r < n && a[r] > a[largest]) largest = r;15 if (largest == i) return;16 std::swap(a[i], a[largest]);17 i = largest;18 }19}20
21void heapSort(std::vector<int>& a) {22 int n = static_cast<int>(a.size());23 // Build a max-heap in place24 for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i);25 // Repeatedly move the max to the end and shrink the heap26 for (int end = n - 1; end > 0; --end) {27 std::swap(a[0], a[end]);28 siftDown(a, end, 0);29 }30}31
32int main() {33 std::vector<int> data = {12, 11, 13, 5, 6, 7};34 std::cout << "Before: ";35 printVec(data);36 heapSort(data);37 std::cout << "After: ";38 printVec(data);39 return 0;40}Codice Heap Sort in C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void siftDown(int a[], int n, int i) {9 while (1) {10 int largest = i, l = 2 * i + 1, r = 2 * i + 2;11 if (l < n && a[l] > a[largest]) largest = l;12 if (r < n && a[r] > a[largest]) largest = r;13 if (largest == i) return;14 int tmp = a[i];15 a[i] = a[largest];16 a[largest] = tmp;17 i = largest;18 }19}20
21void heapSort(int a[], int n) {22 // Build a max-heap in place23 for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);24 // Repeatedly move the max to the end and shrink the heap25 for (int end = n - 1; end > 0; end--) {26 int tmp = a[0];27 a[0] = a[end];28 a[end] = tmp;29 siftDown(a, end, 0);30 }31}32
33int main(void) {34 int data[] = {12, 11, 13, 5, 6, 7};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 heapSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}Domande frequenti sull'heap sort
Qual è la complessità temporale dell'heap sort?
L'heap sort è
O(n log n) nel caso migliore, medio e peggiore. Costruire l'heap costa O(n) e ognuna delle n estrazioni costa O(log n). Usa O(1) di spazio extra.L'heap sort è stabile?
No. L'operazione di sift-down può spostare elementi uguali uno oltre l'altro, quindi l'heap sort non preserva l'ordine relativo delle chiavi uguali.
Quando conviene usare l'heap sort?
Usa l'heap sort quando ti serve un caso peggiore
O(n log n) garantito con solo O(1) di memoria extra. Evita il rischio O(n²) del quicksort senza il buffer O(n) del merge sort, a scapito della stabilità e delle prestazioni di cache.Qual è la differenza tra heap sort e quicksort?
Entrambi ordinano in loco, ma il quicksort ha un caso peggiore
O(n²) mentre l'heap sort garantisce O(n log n). In pratica il quicksort di solito è più veloce grazie a una migliore località di cache e a meno scambi, quindi l'heap sort si preferisce soprattutto quando il limite nel caso peggiore deve essere garantito.Che rapporto c'è tra l'heap sort e una coda di priorità?
Un heap binario è l'implementazione standard di una coda di priorità, e l'heap sort consiste in sostanza nell'estrarre ripetutamente il massimo da quella coda. Se tieni già i tuoi dati in un heap, estrarre gli elementi uno a uno ti dà un ordinamento senza costi extra.
L'heap sort ha bisogno di un max-heap o di un min-heap?
Per ordinare in ordine crescente in loco usa un max-heap: a ogni passata l'elemento più grande viene scambiato in fondo, facendo crescere la coda ordinata da destra. Un min-heap produrrebbe un ordine decrescente in loco, oppure crescente se estrai gli elementi in un array separato.
Risorse correlate
Altre visualizzazioni
