Heaps

Introduzione

Gli heaps (code a priorità) sono una struttura dati basata su un binary tree con proprietà specifiche. A prima vista possono sembrare simili ai binary search trees, ma hanno caratteristiche e regole completamente diverse.

Caratteristiche degli Heaps

Struttura base

Un heap è un binary tree con le seguenti caratteristiche:

1. Complete tree: l’albero è sempre completo, cioè si riempie da sinistra a destra senza gap
2. Heap property: ogni nodo ha un valore maggiore (max heap) o minore (min heap) di tutti i suoi discendenti
3. Duplicati permessi: a differenza dei BST, gli heaps permettono valori duplicati

1
// Esempio di max heap
2
//        [99]
3
//       /    \
4
//    [72]    [61]
5
//    /  \    /  \
6
//  [65] [50] [45] [40]

Max Heap vs Min Heap

• Max Heap: il valore massimo è sempre alla radice. Ogni nodo è maggiore dei suoi discendenti
• Min Heap: il valore minimo è sempre alla radice. Ogni nodo è minore dei suoi discendenti

Nota: In questi appunti implementeremo un max heap.

Complete Tree

Un albero è completo quando:

• Si riempie da sinistra a destra senza gap
• Ogni livello (tranne l’ultimo) è completamente riempito
• L’ultimo livello ha tutti i nodi a sinistra

1
// ✅ Complete tree
2
//        [A]
3
//       /   \
4
//     [B]   [C]
5
//     / \
6
//   [D] [E]
7

8
// ❌ Non completo (gap a destra)
9
//        [A]
10
//       /   \
11
//     [B]   [C]
12
//     /
13
//   [D]

Ordine parziale

A differenza dei BST, gli heaps non hanno un ordine completo. L’unica regola è che ogni nodo deve essere maggiore (o minore) dei suoi discendenti. Questo significa che:

• I nodi al secondo livello possono essere scambiati tra loro e rimanere validi
• Non c’è un ordine specifico tra nodi allo stesso livello
• L’unica garanzia è che il massimo (o minimo) è sempre in cima

1
// Entrambi sono max heap validi:
2
//        [99]              [99]
3
//       /    \            /    \
4
//    [72]    [61]      [61]    [72]
5
//    /  \    /  \      /  \    /  \
6
//  [65] [50] [45] [40] [65] [50] [45] [40]

Implementazione con Array

A differenza dei BST che usano classi Node, gli heaps vengono implementati usando un array. Questo rende l’implementazione più efficiente e semplice.

Rappresentazione in array

I nodi vengono memorizzati nell’array seguendo un ordine specifico:

1. La radice va all’indice 0
2. Si procede livello per livello, da sinistra a destra

1
// Heap tree:
2
//        [99]
3
//       /    \
4
//    [72]    [61]
5
//    /  \    /  \
6
//  [65] [50] [45] [40]
7

8
// Array rappresentazione:
9
[99, 72, 61, 65, 50, 45, 40]
10
// 0   1   2   3   4   5   6

Nota: Esistono due modi comuni:

• Usare index 0: più semplice matematicamente, useremo questo
• Lasciare index 0 vuoto: alcune implementazioni preferiscono questo per formule più intuitive

Complete tree requirement

Il requisito che l’albero sia completo è critico perché:

• Permette di rappresentare l’albero come un array contiguo
• Senza gap, gli indici sono consecutivi
• Se ci fossero gap, non potremmo usare un array semplice

Formule matematiche per la navigazione

Grazie alla struttura completa e alla rappresentazione in array, possiamo calcolare parent e children usando semplici formule matematiche.

Left Child (Figlio sinistro)

1
leftChild(index) = 2 * index + 1

Esempi:

• Index 0 → left child = 2 * 0 + 1 = 1
• Index 1 → left child = 2 * 1 + 1 = 3
• Index 2 → left child = 2 * 2 + 1 = 5

Right Child (Figlio destro)

1
rightChild(index) = 2 * index + 2

Esempi:

• Index 0 → right child = 2 * 0 + 2 = 2
• Index 1 → right child = 2 * 1 + 2 = 4
• Index 2 → right child = 2 * 2 + 2 = 6

Nota: Il right child è sempre leftChild + 1.

Parent (Genitore)

1
parent(index) = Math.floor((index - 1) / 2)

Esempi:

• Index 1 → parent = Math.floor((1 - 1) / 2) = 0
• Index 2 → parent = Math.floor((2 - 1) / 2) = 0
• Index 3 → parent = Math.floor((3 - 1) / 2) = 1
• Index 6 → parent = Math.floor((6 - 1) / 2) = 2

Spiegazione: Usiamo Math.floor() per arrotondare verso il basso, eliminando la parte decimale.

Implementazione

Costruttore del MaxHeap

Il costruttore crea un heap vuoto usando un array privato:

1
class MaxHeap {
2
  constructor() {
3
    // Array privato per memorizzare i valori dell'heap
4
    // Non esponiamo direttamente questo array per evitare modifiche esterne
5
    this.heap = [];
6
  }
7
}

Spiegazione:

• this.heap = []: crea un array vuoto che conterrà tutti i valori
• L’array è privato (non esposto direttamente) per mantenere l’integrità dell’heap

Get Heap - Ottenere una copia dell’heap

Espone una copia dell’heap invece dell’array originale per prevenire modifiche esterne:

1
getHeap() {
2
  // Ritorna una copia dell'array usando spread operator
3
  // Questo previene modifiche dirette all'heap dall'esterno
4
  return [...this.heap];
5
}

Perché una copia?: Se esponessimo direttamente this.heap, il codice esterno potrebbe modificarlo direttamente, rompendo la struttura dell’heap. La copia protegge l’integrità dei dati.

Helper Methods

Prima di implementare insert e remove, creiamo metodi helper per semplificare il codice:

Left Child

1
leftChild(index) {
2
  // Calcola l'indice del figlio sinistro
3
  return 2 * index + 1;
4
}

Right Child

1
rightChild(index) {
2
  // Calcola l'indice del figlio destro
3
  return 2 * index + 2;
4
}

Parent

1
parent(index) {
2
  // Calcola l'indice del genitore
3
  // Math.floor arrotonda verso il basso
4
  return Math.floor((index - 1) / 2);
5
}

Swap

1
swap(index1, index2) {
2
  // Scambia i valori alle due posizioni nell'array
3
  const temp = this.heap[index1];
4
  this.heap[index1] = this.heap[index2];
5
  this.heap[index2] = temp;
6
}

Operazioni

Insert - Inserire un valore

Inserisce un nuovo valore nell’heap mantenendo la proprietà di heap. Complessità: O(log n)

Logica:

1. Aggiungi alla fine: per mantenere l’albero completo, aggiungi il valore alla fine dell’array
2. Bubble up: confronta il valore con il suo parent
3. Scambia se necessario: se il valore è maggiore del parent, scambiali
4. Ripeti: continua finché non raggiungi la radice o il parent è maggiore

Due condizioni per uscire dal loop:

• Il valore raggiunge la radice (index = 0)
• Il parent è maggiore del valore corrente

1
insert(value) {
2
  // Aggiungi il valore alla fine dell'array per mantenere l'albero completo
3
  this.heap.push(value);
4

5
  // current punta all'indice dell'elemento appena inserito
6
  let current = this.heap.length - 1;
7

8
  // Bubble up: sposta il valore verso l'alto finché necessario
9
  while (current > 0) {
10
    // Calcola l'indice del parent
11
    const parentIndex = this.parent(current);
12

13
    // Se il valore corrente è maggiore del parent, scambiali
14
    if (this.heap[current] > this.heap[parentIndex]) {
15
      this.swap(current, parentIndex);
16
      // Aggiorna current per puntare alla nuova posizione
17
      current = parentIndex;
18
    } else {
19
      // Se il parent è maggiore, l'heap è valido, esci dal loop
20
      break;
21
    }
22
  }
23
}

Spiegazione dettagliata:

1. Push: this.heap.push(value) aggiunge il valore alla fine, mantenendo l’albero completo
2. Current: punta all’indice del valore appena inserito
3. While loop: continua finché current > 0 (non abbiamo raggiunto la radice)
4. Confronto: se il valore corrente è maggiore del parent, scambiali
5. Update current: dopo lo swap, current punta alla nuova posizione (il parent)
6. Break: se il parent è maggiore, l’heap è valido e possiamo fermarci

Esempio di utilizzo:

1
const heap = new MaxHeap();
2
heap.insert(50);
3
heap.insert(30);
4
heap.insert(100);  // Bubble up fino alla radice
5
// Risultato: [100, 50, 30]

Remove - Rimuovere il valore massimo

Rimuove e ritorna il valore massimo (radice) dell’heap. Complessità: O(log n)

Logica:

1. Edge cases: gestisci heap vuoto e heap con un solo elemento
2. Salva il massimo: salva il valore alla radice (index 0)
3. Sostituisci con l’ultimo: sposta l’ultimo elemento alla radice per mantenere l’albero completo
4. Sink down: sposta il valore verso il basso confrontandolo con i suoi figli
5. Ritorna il massimo: ritorna il valore salvato

1
remove() {
2
  // Edge case: heap vuoto
3
  if (this.heap.length === 0) {
4
    return null;
5
  }
6

7
  // Edge case: heap con un solo elemento
8
  if (this.heap.length === 1) {
9
    return this.heap.pop();
10
  }
11

12
  // Salva il valore massimo (alla radice)
13
  const maxValue = this.heap[0];
14

15
  // Sostituisci la radice con l'ultimo elemento per mantenere l'albero completo
16
  this.heap[0] = this.heap.pop();
17

18
  // Sink down: sposta il valore verso il basso nella posizione corretta
19
  this.sinkDown(0);
20

21
  // Ritorna il valore massimo
22
  return maxValue;
23
}

Spiegazione dettagliata:

1. Heap vuoto: ritorna null se non ci sono elementi
2. Un solo elemento: rimuovi e ritorna direttamente
3. Salva massimo: il valore alla radice è il massimo
4. Sostituisci: this.heap[0] = this.heap.pop() sposta l’ultimo elemento alla radice
5. Sink down: chiama il metodo helper per riorganizzare l’heap

Sink Down - Metodo helper per remove

Sposta un valore verso il basso confrontandolo con i suoi figli. Complessità: O(log n)

Logica:

1. Confronta il valore corrente con i suoi figli
2. Trova il figlio con il valore maggiore
3. Se il figlio maggiore è più grande del valore corrente, scambiali
4. Continua finché il valore non è nella posizione corretta

1
sinkDown(index) {
2
  // maxIndex punta al nodo con il valore maggiore tra current e i suoi figli
3
  let maxIndex = index;
4
  const size = this.heap.length;
5

6
  // Continua finché non troviamo la posizione corretta
7
  while (true) {
8
    // Calcola gli indici dei figli
9
    const leftIndex = this.leftChild(index);
10
    const rightIndex = this.rightChild(index);
11

12
    // Confronta con il figlio sinistro (se esiste)
13
    if (leftIndex < size && this.heap[leftIndex] > this.heap[maxIndex]) {
14
      maxIndex = leftIndex;
15
    }
16

17
    // Confronta con il figlio destro (se esiste)
18
    if (rightIndex < size && this.heap[rightIndex] > this.heap[maxIndex]) {
19
      maxIndex = rightIndex;
20
    }
21

22
    // Se maxIndex è cambiato, dobbiamo fare uno swap
23
    if (maxIndex !== index) {
24
      this.swap(index, maxIndex);
25
      // Aggiorna index per continuare il sink down
26
      index = maxIndex;
27
    } else {
28
      // Se maxIndex non è cambiato, il valore è nella posizione corretta
29
      return;
30
    }
31
  }
32
}

Spiegazione dettagliata:

1. maxIndex: tiene traccia del nodo con il valore maggiore
2. Validazione indici: controlla che leftIndex < size e rightIndex < size prima di accedere
3. Confronto figli: confronta il valore corrente con entrambi i figli
4. Aggiorna maxIndex: se un figlio è maggiore, aggiorna maxIndex
5. Swap: se maxIndex è cambiato, scambia e continua
6. Return: se maxIndex non è cambiato, il valore è nella posizione corretta

Importante: Dobbiamo sempre verificare che gli indici dei figli siano validi (< size) prima di accedere all’array, altrimenti potremmo accedere a posizioni inesistenti.

Implementazione completa

Ecco il codice completo della classe MaxHeap:

1
class MaxHeap {
2
  constructor() {
3
    // Array privato per memorizzare i valori dell'heap
4
    this.heap = [];
5
  }
6

7
  getHeap() {
8
    // Ritorna una copia dell'array per prevenire modifiche esterne
9
    return [...this.heap];
10
  }
11

12
  leftChild(index) {
13
    // Calcola l'indice del figlio sinistro
14
    return 2 * index + 1;
15
  }
16

17
  rightChild(index) {
18
    // Calcola l'indice del figlio destro
19
    return 2 * index + 2;
20
  }
21

22
  parent(index) {
23
    // Calcola l'indice del genitore
24
    return Math.floor((index - 1) / 2);
25
  }
26

27
  swap(index1, index2) {
28
    // Scambia i valori alle due posizioni
29
    const temp = this.heap[index1];
30
    this.heap[index1] = this.heap[index2];
31
    this.heap[index2] = temp;
32
  }
33

34
  insert(value) {
35
    // Aggiungi il valore alla fine dell'array
36
    this.heap.push(value);
37
    let current = this.heap.length - 1;
38

39
    // Bubble up: sposta il valore verso l'alto
40
    while (current > 0) {
41
      const parentIndex = this.parent(current);
42
      if (this.heap[current] > this.heap[parentIndex]) {
43
        this.swap(current, parentIndex);
44
        current = parentIndex;
45
      } else {
46
        break;
47
      }
48
    }
49
  }
50

51
  remove() {
52
    // Edge case: heap vuoto
53
    if (this.heap.length === 0) {
54
      return null;
55
    }
56

57
    // Edge case: heap con un solo elemento
58
    if (this.heap.length === 1) {
59
      return this.heap.pop();
60
    }
61

62
    // Salva il valore massimo
63
    const maxValue = this.heap[0];
64

65
    // Sostituisci la radice con l'ultimo elemento
66
    this.heap[0] = this.heap.pop();
67

68
    // Sink down: riorganizza l'heap
69
    this.sinkDown(0);
70

71
    // Ritorna il valore massimo
72
    return maxValue;
73
  }
74

75
  sinkDown(index) {
76
    let maxIndex = index;
77
    const size = this.heap.length;
78

79
    while (true) {
80
      const leftIndex = this.leftChild(index);
81
      const rightIndex = this.rightChild(index);
82

83
      // Confronta con il figlio sinistro (se esiste)
84
      if (leftIndex < size && this.heap[leftIndex] > this.heap[maxIndex]) {
85
        maxIndex = leftIndex;
86
      }
87

88
      // Confronta con il figlio destro (se esiste)
89
      if (rightIndex < size && this.heap[rightIndex] > this.heap[maxIndex]) {
90
        maxIndex = rightIndex;
91
      }
92

93
      // Se maxIndex è cambiato, scambia e continua
94
      if (maxIndex !== index) {
95
        this.swap(index, maxIndex);
96
        index = maxIndex;
97
      } else {
98
        // Il valore è nella posizione corretta
99
        return;
100
      }
101
    }
102
  }
103
}

Priority Queue

Un Priority Queue è una struttura dati che ritorna sempre l’elemento con la priorità più alta. Gli heaps sono la struttura dati più comune per implementare priority queue.

Perché usare Heaps per Priority Queue?

Confrontiamo le complessità delle operazioni principali:

Vantaggi degli Heaps:

• Sempre bilanciato: grazie alla proprietà di complete tree, l’altezza è sempre log n
• Garantito O(log n): a differenza dei BST, non può degenerare in O(n)
• Efficiente: insert e remove sono entrambi O(log n)

Altezza dell’albero: L’altezza di un heap completo è sempre log₂(n), dove n è il numero di nodi. Questo significa che:

• Insert: bubble up al massimo log n livelli → O(log n)
• Remove: sink down al massimo log n livelli → O(log n)

Complessità temporale (Big O)

Nota: L’efficienza deriva dal fatto che l’albero è sempre completo, quindi l’altezza è sempre log n, garantendo operazioni O(log n).

Quando usare Heaps

Usa un Heap quando:

• Devi implementare una Priority Queue: sempre ritornare l’elemento con priorità più alta
• Hai bisogno di operazioni O(log n) garantite: a differenza dei BST, gli heaps sono sempre bilanciati
• Non hai bisogno di ricerca per valore: gli heaps non supportano ricerca efficiente (O(n))
• Hai bisogno di duplicati: gli heaps permettono valori duplicati

Esempi pratici:

1. Scheduling di processi: processi con priorità diverse
2. Dijkstra’s Algorithm: trova il percorso più breve
3. Merge K sorted arrays: fusione efficiente di array ordinati
4. Event simulation: eventi con timestamp diversi
5. Load balancing: distribuire carichi in base alla priorità

Non usare un Heap quando:

• Hai bisogno di ricerca per valore: usa BST o Hash Table
• Hai bisogno di accesso casuale: gli heaps non supportano accesso per indice
• Hai bisogno di ordinamento completo: gli heaps mantengono solo ordine parziale

Esercizi e problemi comuni

Per praticare e approfondire gli heaps, consulta la sezione dedicata agli esercizi e problemi comuni