KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / Python

heapq.heapify

Bouwt in lineaire tijd een min-heap uit een bestaande lijst.

Versie: Python 3.14; repository image, production runtime not attested

Syntax

heapq.heapify(heap, /)

Bouwt in lineaire tijd een min-heap uit een bestaande lijst.

Elke ouder is kleiner dan of gelijk aan elk van zijn aanwezige kinderen. De functie herschikt dezelfde lijst en geeft None terug. Elementen moeten met < vergelijkbaar zijn. De wortel bevat het minimum en de kinderen van dezelfde ouder hebben onderling geen vaste volgorde.

In het voorbeeld geeft index 0 de waarde 1 en herhaald verwijderen geeft 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)))

Voorbeelden

import heapq
items = [8, 3, 7, 1]
print(heapq.heapify(items))
print(items[0], [heapq.heappop(items) for _ in range(4)])

Resultaat

None
1 [1, 3, 7, 8]

In het voorbeeld geeft index 0 de waarde 1 en herhaald verwijderen geeft 1, 3, 7, 8.

Bronnen