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