Heap : le min ou le max en O(1)
AvancéLa structure derrière les files de priorité et les problèmes de « top k ».
Un heap est un arbre binaire quasi complet où chaque parent est plus petit (min-heap) ou plus grand (max-heap) que ses enfants : le minimum (ou maximum) est toujours à la racine. Il s'implémente sur un simple tableau : les enfants de i sont en 2i+1 et 2i+2.
| Opération | Complexité |
|---|---|
| Lire le min / max | O(1) |
| Insérer, retirer le min / max | O(log n) |
| Construire à partir de n éléments | O(n) |
Top k : les k plus grands éléments#
On garde un min-heap de taille k : si un nouvel élément dépasse le plus petit du heap, il le remplace. Complexité O(n log k) et mémoire O(k), sans trier tout le tableau.
// JavaScript n'a pas de heap natif : voici un min-heap minimal.
class MinHeap {
private data: number[] = [];
get size() { return this.data.length; }
peek() { return this.data[0]; }
push(x: number): void {
const d = this.data;
d.push(x);
let i = d.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (d[p] <= d[i]) break;
[d[p], d[i]] = [d[i], d[p]];
i = p;
}
}
pop(): number {
const d = this.data;
const top = d[0];
const last = d.pop()!;
if (d.length) {
d[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < d.length && d[l] < d[m]) m = l;
if (r < d.length && d[r] < d[m]) m = r;
if (m === i) break;
[d[m], d[i]] = [d[i], d[m]];
i = m;
}
}
return top;
}
}
function topK(nums: number[], k: number): number[] {
const heap = new MinHeap();
for (const x of nums) {
heap.push(x);
if (heap.size > k) heap.pop(); // évince le plus petit
}
const result: number[] = [];
while (heap.size) result.push(heap.pop());
return result.reverse(); // du plus grand au plus petit
}
Astuce : Python n'a qu'un min-heap ; pour un max-heap, insérez les valeurs négées. Autres cas d'usage : file de priorité (tâches par urgence), fusion de k listes triées, médiane en flux (deux heaps), plus court chemin de Dijkstra.