Imparare gli algoritmi

Capitolo 4. L'abbondanza

Questo lavoro è stato tradotto utilizzando l'AI. Siamo lieti di ricevere il tuo feedback e i tuoi commenti: [e-mail]

In questo capitolo imparerai:

• I tipi di dati della coda e della coda prioritaria.

• La struttura dati binaria heap, inventata nel 1964, che può essere memorizzata in un array.

• In un heap binario max, una voce con priorità numerica maggiore è considerata più prioritaria di una voce con priorità numerica minore. In un heap binario min, le voci con priorità numerica minore hanno una priorità maggiore.

• Come inserire una voce (valore, priorità) in un heap binario in O(log N), dove N è il numero di voci nell'heap.

• Come trovare il valore con priorità più alta in un heap binario in O(1).

• Come rimuovere il valore con priorità più alta da un heap binario in O(log N).

Invece di memorizzare un insieme di valori, cosa succederebbe se si memorizzasse un insieme di voci, dove ogni voce ha un valore e unapriorità associata rappresentata da un numero? Date due voci, quella la cui priorità è più alta è più importante dell'altra. La sfida di questa volta è quella di rendere possibile l'inserimento di nuove voci (valore, priorità) in una collezione e di poter rimuovere e restituire il valore della voce con priorità più alta dalla collezione.

Questo comportamento definisce una coda di priorità, untipo di dati che supporta in modo efficiente enqueue(value, priority) e dequeue(), che rimuove il valore con la priorità più alta. ...