5.12 `heapq` -- Algoritmo heap queue

Nuovo nella versione 2.3.

Questo modulo fornisce un'implementazione dell'algoritmo heap queue, conosciuto anche come algoritmo di coda con priorit�.

Gli Heap sono vettori tali che heap[k] <= heap[2*k+1] e heap[k] <= heap[2*k+2] per ogni k, contando gli elementi da zero. Per esigenze di confronto, gli elementi non presenti vengono considerati infiniti, quindi maggiori di qualunque altro. L'interessante propriet� dello heap � che heap[0] � sempre l'elemento pi� piccolo.

L'API seguente differisce dagli algoritmi di heap dei manuali informatici per due aspetti: (a) Noi usiamo indici che iniziano da zero. Questo rende le relazioni tra l'indice di un nodo e gli indici dei suoi figli leggermente meno ovvie, ma � pi� conveniente poich� anche Python usa indicizza da zero. (b) Il nostro metodo pop restituisce l'elemento pi� piccolo, non il pi� grande (chiamato il "min heap" nei manuali; un "max heap" � pi� comune nei testi grazie alla sua adattabilit� all'ordinamento sul posto).

Questi due punti permettono di trattare l'heap come una normale lista Python senza sorprese: heap[0] � l'elemento pi� piccolo e heap.sort() mantiene l'heap invariato!

Per creare uno heap, potete utilizzare una lista inizializzata a [] o trasformare una lista non vuota in uno heap tramite la funzione heapify().

Vengono fornite le seguenti funzioni :

heappush( heap, item): Inserisce il valore item in heap, mantenendo invariato lo heap.

heappop( heap): Estrae e restituisce il pi� piccolo elemento di heap, mantenendo lo heap invariato. Se lo heap � vuoto, viene sollevata l'eccezione IndexError.

heapify( x): Trasforma la lista x in uno heap, sul posto, in un tempo lineare.

heapreplace( heap, item): Estrae e restituisce il pi� piccolo elemento di heap e vi introduce un nuovo elemento, item. La dimensione dello heap non cambia. Se lo heap � vuoto, viene sollevata un'eccezione IndexError. Questa funzione � pi� efficiente di heappop() seguita da heappush() e pu� essere pi� adatta quando si usa uno heap di dimensione fissa. Notate che il valore restituito pu� essere pi� grande di item! Per cui utilizzate attentamente questa procedura.

Esempio di utilizzo:

>>> from heapq import heappush, heappop
>>> heap = []
>>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
>>> for item in data:
...     heappush(heap, item)
...
>>> sorted = []
>>> while heap:
...     sorted.append(heappop(heap))
...
>>> print sorted
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> data.sort()
>>> print data == sorted
True
>>>

Vedete Circa questo documento... per informazioni su modifiche e suggerimenti.

5.12 heapq -- Algoritmo heap queue

5.12 `heapq` -- Algoritmo heap queue