#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.