Un heap è una struttura dati di tipo ad albero nella quale i nodi figli hanno una relazione di ordinamento con i genitori. Gli heap binari possono essere rappresentati usando una lista oppure un array organizzato in modo che i figli dell'elemento N siano alle posizioni 2 * N + 1 e 2 * N + 2 (per indici a base zero). Questa disposizione rende possibile riordinare gli elementi sul posto, in modo che non sia necessario riallocare tanta memoria quanta ne servirebbe per aggiungere o rimuovere elementi.

Un max-heap assicura che il genitore sia più grande od uguale ad entrambi i figli. Un min-heap richiede che il genitore sia minore od uguale ai suoi figli. Il modulo heapq di Python implementa min-heap.

Dati di Esempio

Gli esempi in questa sezione utilizzano i dati in heapq_heapdata.py.

# heapq_heapdata.py

# Questi dati osono stati generati con il modulo random.

data = [19, 9, 4, 10, 11]

Il risultato è stampato usando heapq_showtree.py.

# heapq_showtree.py

import math
from io import StringIO


def show_tree(tree, total_width=36, fill=' '):
    """Stampa formattata di un albero."""
    output = StringIO()
    last_row = -1
    for i, n in enumerate(tree):
        if i:
            row = int(math.floor(math.log(i + 1, 2)))
        else:
            row = 0
        if row != last_row:
            output.write('\n')
        columns = 2 ** row
        col_width = int(math.floor(total_width / columns))
        output.write(str(n).center(col_width, fill))
        last_row = row
    print(output.getvalue())
    print('-' * total_width)
    print()

Creare un Heap

Ci sono due metodi base per creare un heap: heappush() ed heapify().

# heapq_heappush.py

import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data

heap = []
print('casuali :', data)
print()

for n in data:
    print('aggiungo {:>3}:'.format(n))
    heapq.heappush(heap, n)
    show_tree(heap)

Quando viene usato heappush(), il tipo di ordinamento dell'heap viene mantenuto mentre vengono aggiunti nuovi elementi alla sorgente dati.

$ python3 heapq_heappush.py

casuali : [19, 9, 4, 10, 11]

aggiungo  19:

                 19                 
------------------------------------

aggiungo   9:

                 9                  
        19        
------------------------------------

aggiungo   4:

                 4                  
        19                9         
------------------------------------

aggiungo  10:

                 4                  
        10                9         
    19   
------------------------------------

aggiungo  11:

                 4                  
        10                9         
    19       11   
------------------------------------

Se i dati sono già in memoria, è più efficace l'uso di heapify() per ricollocare gli elementi della lista sul posto.

# heapq_heapify.py

import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data

print('casuali :', data)
heapq.heapify(data)
print('con heap:')
show_tree(data)

La costruzione di una lista con l'ordinamento heap un elemento alla volta equivale alla costruzione di una lista non ordinata e la successiva chiamata di heapify().

$ python3 heapq_heapify.py

casuali : [19, 9, 4, 10, 11]
con heap:

                 4                  
        9                 19        
    10       11   
------------------------------------

Accedere ai Contenuti di un Heap

Una volta che l'heap viene organizzato correttamente, si usi heappop() per rimuovere l'elemento con il valore più basso.

# heapq_heappop.py

import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data

print('casuale :', data)
heapq.heapify(data)
print('con heap:')
show_tree(data)
print()

for i in range(2):
    smallest = heapq.heappop(data)
    print('rimosso {:>3}:'.format(smallest))
    show_tree(data)

In questo esempio, adattato dalla documentazione della libreria standard, heapify() ed heappop() sono usati per ordinare una lista di numeri.

$ python3 heapq_heappop.py

casuale : [19, 9, 4, 10, 11]
con heap:

                 4                  
        9                 19        
    10       11   
------------------------------------


rimosso   4:

                 9                  
        10                19        
    11   
------------------------------------

rimosso   9:

                 10                 
        11                19        
------------------------------------

Per rimuovere elementi esistenti e sostituirli con nuovi valori in una singola operazione, si usi heapreplace().

# heapq_heapreplace.py

import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data

heapq.heapify(data)
print('inizio:')
show_tree(data)

for n in [0, 13]:
    smallest = heapq.heapreplace(data, n)
    print('sostituzione di  {:>2} con {:>2}:'.format(smallest, n))
    show_tree(data)

La sostituzione di elementi sul posto rende possibile il mantenimento di un heap a dimensione fissa, come ad esempio una lista di lavorazioni ordinate per priorità.

$ python3 heapq_heapreplace.py

inizio:

                 4                  
        9                 19        
    10       11   
------------------------------------

sostituzione di   4 con  0:

                 0                  
        9                 19        
    10       11   
------------------------------------

sostituzione di   0 con 13:

                 9                  
        10                19        
    13       11   
------------------------------------

Estremi dei Dati da un Heap

heapq include due funzioni per esaminare un oggetto iterabile e trovare l'intervallo tra il valore più piccolo e quello più grande in esso contenuti.

# heapq_extremes.py

import heapq
from heapq_heapdata import data

print('tutti          :', data)
print('3 più grandi   :', heapq.nlargest(3, data))
print('da ordinamento :', list(reversed(sorted(data)[-3:])))
print('3 più piccoli  :', heapq.nsmallest(3, data))
print('da ordinamento :', sorted(data)[:3])

L'uso di nlargest() e nsmallest() per trovare il valore rispettivamente più grande e più piccolo è efficace solo in presenza di valori relativamente piccoli di n > 1, ma in alcuni casi può essere utile.

$ python3 heapq_extremes.py

tutti          : [19, 9, 4, 10, 11]
3 più grandi   : [19, 11, 10]
da ordinamento : [19, 11, 10]
3 più piccoli  : [4, 9, 10]
da ordinamento : [4, 9, 10]

Combinare con Efficacia Sequenze Ordinate

La combinazione di parecchie sequenze ordinate in una nuova sequenza è facile per piccoli insiemi di dati.

list(sorted(itertools.chain(*data)))

Per insiemi di dati più grandi, questa tecnica può richiedere l'uso di un ammontare di memoria considerevole. Invece di ordinare l'intera sequenza combinata, merge() usa un heap per generare una nuova sequenza un elemento alla volta, determinando il successivo usando un ammontare di memoria fisso.

# heapq_merge.py

import heapq
import random


random.seed(2016)

data = []
for i in range(4):
    new_data = list(random.sample(range(1, 101), 5))
    new_data.sort()
    data.append(new_data)

for i, d in enumerate(data):
    print('{}: {}'.format(i, d))

print('\nCombinati:')
for i in heapq.merge(*data):
    print(i, end=' ')
print()

Visto che l'implementazione di merge() usa un heap, consuma memoria in base al numero di sequenze che si devono combinare, invece che in base al numero di elementi con i quali sono composte dette sequenze.

$ python3 heapq_merge.py

0: [33, 58, 71, 88, 95]
1: [10, 11, 17, 38, 91]
2: [13, 18, 39, 61, 63]
3: [20, 27, 31, 42, 45]

Combinati:
10 11 13 17 18 20 27 31 33 38 39 42 45 58 61 63 71 88 91 95