#code #algorithme
Les heaps sont des structures de données en tree satisfaisant la “heap property” : chaque node parent est plus petit ou égal à ses nodes enfants.
Il est possible de représenter une heap avec un Binary Tree, ou avec un array. Dans l’array:
- le 1er élément de l’array est le root
- les enfants d’un node i
sont 2i
et 2i + 1
- le parent d’un node i
est i/2
Une Heap permet d’implémenter un Priority Queue dont les opérations sont en O(log(n))
, utile notamment pour l’[[2023-10-13 Algorithme de Dijkstra|l’algorithme de Dijkstra]].
Cela permet également de réaliser un “heap sort”, un sort en O(n*log(n))
qui n’utilise pas de mémoire supplémentaire.