Heap (heap binario)
Ultimo aggiornamento
Un heap binario è un albero binario completo che tiene alla radice il valore più piccolo (min-heap) o più grande (max-heap). Questa visualizzazione è un min-heap: ogni genitore è minore o uguale ai suoi figli. Per aggiungere un valore lo metti nella prossima posizione libera, poi lo "fai risalire" (sift-up) scambiandolo con il genitore finché è più piccolo, fino a quando la proprietà di heap torna a valere. Premi play qui sopra per vedere ogni nuovo valore risalire fino al suo posto.
Dato che un heap è un albero completo, si memorizza in modo compatto in un array: i figli del nodo i stanno in 2i+1 e 2i+2. Inserimento e rimozione del minimo sono O(log n) (un solo percorso dalla radice a una foglia), mentre leggere il minimo è O(1): esattamente ciò che serve a una coda di priorità.
Complessità temporale e spaziale
| Operazione | Complessità | Note |
|---|---|---|
| Leggere min/max | O(1) | È sempre la radice |
| Inserimento (push) | O(log n) | Sift-up lungo un percorso |
| Rimozione min/max | O(log n) | Sift-down lungo un percorso |
| Costruzione dell'heap | O(n) | Heapify tutto in una volta |
| Spazio | O(n) | Basato su array, senza puntatori |
Passo dopo passo (push)
| Passo | Cosa succede |
|---|---|
| 1 | Aggiungi il nuovo valore in fondo (prossima foglia libera). |
| 2 | Confrontalo con il suo genitore. |
| 3 | Se è più piccolo (min-heap), scambialo verso l'alto. |
| 4 | Ripeti finché non è più piccolo del genitore o raggiunge la radice. |
Esempio svolto
Costruzione di un min-heap inserendo [5, 3, 8, 1, 4] un valore alla volta:
| Push | Array dopo il sift-up | Azione |
|---|---|---|
5 | [5] | Il primo valore diventa la radice. |
3 | [3, 5] | 3 < genitore 5, quindi sale fino alla radice. |
8 | [3, 5, 8] | 8 > genitore 5, quindi resta una foglia. |
1 | [1, 3, 8, 5] | 1 < genitore 5, scambia; poi 1 < genitore 3, scambia fino alla radice. |
4 | [1, 3, 8, 5, 4] | 4 > genitore 3, quindi resta lì; il minimo 1 rimane alla radice. |
Quando usare un heap
| Usalo quando | Evitalo quando |
|---|---|
| Ti serve ripetutamente l'elemento più piccolo o più grande di un insieme che cambia. | Devi cercare valori arbitrari, non solo l'estremo: usa un BST o un hash set. |
| Stai implementando una coda di priorità per Dijkstra, A* o uno scheduler. | Ti servono i dati sempre completamente ordinati. |
Vuoi inserimento e rimozione del minimo O(log n) con una struttura compatta ad array. | Ti serve cercare o rimuovere velocemente un elemento specifico (non la radice). |
| Devi unire un flusso di elementi ed estrarli per priorità. | L'insieme di dati è minuscolo e una scansione lineare è più semplice e abbastanza veloce. |
Codice Heap (Priority Queue)
Un'implementazione di Heap (Priority Queue) 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 (Priority Queue) in Python
Python
1class MinHeap:2 def __init__(self):3 self.data = []4
5 def push(self, value):6 # Append at the end, then bubble up to restore order7 self.data.append(value)8 i = len(self.data) - 19 while i > 0:10 parent = (i - 1) // 211 if self.data[parent] <= self.data[i]:12 break13 self.data[i], self.data[parent] = self.data[parent], self.data[i]14 i = parent15
16 def pop(self):17 # Move the last leaf to the root, then sift it down18 top = self.data[0]19 last = self.data.pop()20 if self.data:21 self.data[0] = last22 self._sift_down(0)23 return top24
25 def _sift_down(self, i):26 n = len(self.data)27 while True:28 smallest = i29 left, right = 2 * i + 1, 2 * i + 230 if left < n and self.data[left] < self.data[smallest]:31 smallest = left32 if right < n and self.data[right] < self.data[smallest]:33 smallest = right34 if smallest == i:35 return36 self.data[i], self.data[smallest] = self.data[smallest], self.data[i]37 i = smallest38
39
40heap = MinHeap()41for value in [5, 3, 8, 1, 9, 2]:42 heap.push(value)43
44print("Heap array: ", heap.data)45print("Popped in order:", [heap.pop() for _ in range(6)])Codice Heap (Priority Queue) in JavaScript
JavaScript
1class MinHeap {2 constructor() {3 this.items = [];4 }5
6 push(value) {7 this.items.push(value);8 // Bubble the new value up while it is smaller than its parent9 let i = this.items.length - 1;10 while (i > 0) {11 const parent = Math.floor((i - 1) / 2);12 if (this.items[parent] <= this.items[i]) break;13 [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];14 i = parent;15 }16 }17
18 pop() {19 const top = this.items[0];20 const last = this.items.pop();21 if (this.items.length > 0) {22 this.items[0] = last;23 this.sinkDown(0);24 }25 return top;26 }27
28 sinkDown(i) {29 const n = this.items.length;30 while (true) {31 let smallest = i;32 const left = 2 * i + 1;33 const right = 2 * i + 2;34 if (left < n && this.items[left] < this.items[smallest]) smallest = left;35 if (right < n && this.items[right] < this.items[smallest]) smallest = right;36 if (smallest === i) return;37 [this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];38 i = smallest;39 }40 }41}42
43const heap = new MinHeap();44for (const value of [5, 2, 9, 1, 7, 3]) heap.push(value);45const sorted = [];46while (heap.items.length > 0) sorted.push(heap.pop());47console.log("Popped in order:", sorted.join(" "));Codice Heap (Priority Queue) in Java
Java
1public class Main {2 static int[] heap = new int[32];3 static int size = 0;4
5 static void push(int value) {6 heap[size] = value;7 int i = size++;8 // Sift up while smaller than the parent9 while (i > 0 && heap[(i - 1) / 2] > heap[i]) {10 swap(i, (i - 1) / 2);11 i = (i - 1) / 2;12 }13 }14
15 static int pop() {16 int min = heap[0];17 heap[0] = heap[--size];18 int i = 0;19 // Sift down: swap with the smaller child until in place20 while (true) {21 int smallest = i, l = 2 * i + 1, r = 2 * i + 2;22 if (l < size && heap[l] < heap[smallest]) smallest = l;23 if (r < size && heap[r] < heap[smallest]) smallest = r;24 if (smallest == i) break;25 swap(i, smallest);26 i = smallest;27 }28 return min;29 }30
31 static void swap(int a, int b) {32 int tmp = heap[a];33 heap[a] = heap[b];34 heap[b] = tmp;35 }36
37 public static void main(String[] args) {38 int[] values = {9, 4, 7, 1, 8, 2};39 for (int v : values) push(v);40 System.out.print("Popped in order:");41 while (size > 0) System.out.print(" " + pop());42 System.out.println();43 }44}Codice Heap (Priority Queue) in C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5struct MinHeap {6 std::vector<int> data;7
8 void push(int value) {9 data.push_back(value);10 // Sift up until the parent is no larger11 size_t i = data.size() - 1;12 while (i > 0) {13 size_t parent = (i - 1) / 2;14 if (data[parent] <= data[i]) break;15 std::swap(data[parent], data[i]);16 i = parent;17 }18 }19
20 int pop() {21 int top = data[0];22 data[0] = data.back();23 data.pop_back();24 // Sift down: swap with the smaller child25 size_t i = 0;26 while (true) {27 size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;28 if (l < data.size() && data[l] < data[smallest]) smallest = l;29 if (r < data.size() && data[r] < data[smallest]) smallest = r;30 if (smallest == i) break;31 std::swap(data[i], data[smallest]);32 i = smallest;33 }34 return top;35 }36
37 int peek() const { return data[0]; }38 bool empty() const { return data.empty(); }39};40
41int main() {42 MinHeap heap;43 for (int value : {5, 3, 8, 1, 9, 2}) heap.push(value);44 std::cout << "Min: " << heap.peek() << "\n";45 std::cout << "Popped in order: ";46 while (!heap.empty()) std::cout << heap.pop() << " ";47 std::cout << "\n";48 return 0;49}Codice Heap (Priority Queue) in C
C
1#include <stdio.h>2
3#define CAP 644
5int heap[CAP];6int heapSize = 0;7
8void push(int value) {9 // Sift up until the parent is no larger10 int i = heapSize++;11 heap[i] = value;12 while (i > 0) {13 int parent = (i - 1) / 2;14 if (heap[parent] <= heap[i]) break;15 int tmp = heap[parent];16 heap[parent] = heap[i];17 heap[i] = tmp;18 i = parent;19 }20}21
22int pop(void) {23 int top = heap[0];24 heap[0] = heap[--heapSize];25 // Sift down: swap with the smaller child26 int i = 0;27 while (1) {28 int l = 2 * i + 1, r = 2 * i + 2, smallest = i;29 if (l < heapSize && heap[l] < heap[smallest]) smallest = l;30 if (r < heapSize && heap[r] < heap[smallest]) smallest = r;31 if (smallest == i) break;32 int tmp = heap[i];33 heap[i] = heap[smallest];34 heap[smallest] = tmp;35 i = smallest;36 }37 return top;38}39
40int main(void) {41 int values[] = {5, 3, 8, 1, 9, 2};42 for (int i = 0; i < 6; i++) push(values[i]);43 printf("Min: %d\n", heap[0]);44 printf("Popped in order: ");45 while (heapSize > 0) printf("%d ", pop());46 printf("\n");47 return 0;48}Domande frequenti sull'heap
A cosa serve un heap?
Gli heap implementano le code di priorità, che fanno funzionare l'algoritmo del cammino minimo di Dijkstra, gli scheduler dei task e le simulazioni a eventi. Sono anche il motore dell'heapsort. Ogni volta che ti serve ripetutamente l'elemento più piccolo o più grande di un insieme che cambia, l'heap è lo strumento giusto.
Qual è la differenza tra un heap e un albero binario di ricerca?
Sono entrambi alberi binari, ma un BST mantiene un ordine completo da sinistra a destra (che rende possibile la ricerca ordinata), mentre un heap garantisce solo la relazione genitore-figlio (minimo o massimo alla radice). Un heap dà accesso O(1) al valore estremo; un BST dà una ricerca O(log n) per qualsiasi valore.
Perché un heap si memorizza in un array?
Dato che un heap è sempre un albero binario completo, i suoi nodi corrispondono perfettamente agli indici di un array: i figli dell'indice
i stanno in 2i+1 e 2i+2, e il genitore in (i-1)/2. Così non devi memorizzare puntatori ai figli e ottieni ottime prestazioni di cache.Un heap è la stessa cosa di un array ordinato?
No. Un heap garantisce solo che ogni genitore sia più piccolo (min-heap) o più grande (max-heap) dei suoi figli, quindi fratelli e cugini non hanno un ordine particolare. Un array ordinato è completamente ordinato ma un inserimento costa
O(n), mentre un heap inserisce in O(log n) dando comunque accesso immediato al valore estremo.Quando conviene usare un heap invece di ordinare un array?
Scegli un heap quando i dati continuano a cambiare e ti serve sempre e solo il minimo o il massimo corrente: inserire ed estrarre costano
O(log n) ciascuno, invece di riordinare tutto l'array. Se hai un insieme di dati statico e vuoi tutti gli elementi in ordine, un singolo ordinamento O(n log n) è più semplice e spesso più veloce.Costruire un heap da n elementi richiede O(n log n)?
No, se lo costruisci tutto in una volta. Inserire
n elementi uno per uno è O(n log n), ma l'heapify dal basso verso l'alto, che fa il sift-down dall'ultimo genitore fino alla radice, richiede O(n) in totale, perché la maggior parte dei nodi sta vicino al fondo e scende solo di poco.Risorse correlate
Altre visualizzazioni
