Code di Priorità, cosa sono, operazioni

Introduzione

Una coda di priorità è una strutura dati contenente un insieme di elementi, dove ad ognuno di essi, si associa un valore di riferimento detto key.
Questa tipologia di struttura dati si implementa solitamente sugli heap.
La coda di priorità si utilizza per gestire i dati secondo un ordine particolare: pensiamo ad esempio all’ordine di esecuzione dei task che vengono seguiti durante l’accesione di un sistema.

Operazioni

Esistono quattro operazioni principali che possiamo fare attraverso una coda di priorità: insertion, maximum, extract-max e increase-key.

• Insert(S, x): inserisce un elemento x all’interno di un insieme S, che è l’insieme degli elementi della coda.
• Maximum(S): restituisce l’elemento con il valore di priorità massima.
• Extract-Max(S): rimuove e restituisce l’elemento con il valore di priorità massima.
• Increase-Key(S, x, k): aumenta il valore di priorità dell’elemento x al valore k, assumendo che x ≤ k.

Andiamo a scrivere gli pseudocodici di queste operazioni ispirate dal libro Introduzione agli Algoritmi

Iniziamo prima dalla seconda procedura, dato che per l’insert serve affrontarne prima un’altra. Maximum(S). Questa procedura è banale, perché basta ritornare il primo elemento del max-heap in questione, ed ha ovviamente un costo costante.

Heap-Maximum(A)

    return A[1]

Passiamo adesso alla procedura Extract-Max(S). Possiamo osservare che è simile al corpo del cliclo for dell’heapsort.
Costo: O(log n) per via del Max-Heapify.

Heap-Extract-Max(A)

    if (A.heapsize < 1)
        error "heap underflow"
    max = A[1]
    A[1] = A[A.heapsize]
    A.heapsize = A.heapsize - 1
    Max-Heapify(A, 1)
    return max

La procedura Increase-Key(S, x, k) che, viene rinominata solitamente Heap-Increase-Key, cambia il valore x in k in tempo costante, subito dobbiamo però verificare se le proprietà dell’heap sono state violate, se sono state violate dovremo sistemare la diposizione dei valori, confrontando il valore con il padre (o i padri).
Complessità: O(log n)

Heap-Increase-Key(A, i, key)

        if (key < A[i])
            error "new key is smaller thean current key"
        A[i] = key
        while (i > 1 and A[Parent(i)] < A[i])
            exchange A[i] with A[Parent(i)]
            i = Parent(i)

Per ultimo vediamo Insert(S, x), che sfrutta la procedura vista precedentemente, per eventualmente riorganizzare l’array e ripristinare le proprietà dell’heap.
Complessità: O(log n)

Max-Heap-Insert(A, key)

    A.heapsize = A.heapsize + 1
    A[A.heapsize] = -∞
    Heap-Increase-Key(A, A.heapsize, key)