Qu'est-ce qu'un heap et comment implémente-t-il une file de priorité ?

Question

IT Interview Practice · Accepted Answer

Un **binary heap** est un arbre binaire complet stocké dans un array qui maintient la **heap property** : dans un **min-heap**, chaque parent est ≤ ses enfants, donc le **minimum se trouve toujours à la racine**. C'est l'implémentation standard d'une **priority queue**.

## Array layout

```text
       1               index: 0  1  2  3  4
      / \              array: [1, 3, 5, 8, 4]
     3   5             parent(i) = (i-1)//2
    / \                left(i)   = 2i+1
   8   4               right(i)  = 2i+2
```

## Operations

```python
import heapq
h = []
heapq.heappush(h, 5)   # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0]        # peek min -> O(1)
heapq.heappop(h)       # O(log n) — remove root, sift down -> 1
```

## Complexity

| Operation | Time |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| build heap from n items | O(n) |

## When to use

- **Scheduling** par priorité (ex. task schedulers du système d'exploitation).
- **Dijkstra / Prim** algorithmes de plus court chemin et arbre couvrant minimal.
- Problèmes **Top-K** et médianes en streaming.
- **Heap sort** (en place O(n log n)).

## Pourquoi c'est important

Un heap vous donne l'élément suivant le plus important instantanément sans garder tout entièrement trié, ce qui est beaucoup moins coûteux que de re-trier.

C'est la base des algorithmes pilotés par priorité et un outil d'entrevue fréquent pour les questions « k plus grand/plus petit ».

Operation	Time
peek min/max	O(1)
push (insert)	O(log n)
pop (extract)	O(log n)
build heap from n items	O(n)

Array layout

Operations

Complexity

When to use

Pourquoi c'est important

Questions connexes