CKTIS / Python
heapq.heapify
Construit en temps linéaire un tas minimal à partir d’une liste.
Version : Python 3.14; repository image, production runtime not attested
Syntaxe
heapq.heapify(heap, /)Construit en temps linéaire un tas minimal à partir d’une liste.
Chaque parent est inférieur ou égal à chacun de ses enfants présents. La fonction réorganise la liste sur place et renvoie None. Les éléments doivent être comparables avec <. La racine est minimale et l’ordre entre frères est libre.
Dans l’exemple l’indice 0 donne 1, puis les extractions successives donnent 1, 3, 7, 8.
from heapq import heapify, heappop
h = [9, 1, 8, 3, 3]
assert heapify(h) is None
assert [heappop(h) for _ in range(5)] == [1, 3, 3, 8, 9]
assert heapify(h) is None and h == []
h = [4, 2, 2, 8, 1]
heapify(h)
assert all(h[(i-1)//2] <= h[i] for i in range(1, len(h)))
Exemples
import heapq
items = [8, 3, 7, 1]
print(heapq.heapify(items))
print(items[0], [heapq.heappop(items) for _ in range(4)])
Résultat
None 1 [1, 3, 7, 8]
Dans l’exemple l’indice 0 donne 1, puis les extractions successives donnent 1, 3, 7, 8.