[Usado em Algoritmo de Dijkstra, Algoritmo de Prim, Fluxo máximo.]
Este módulo PQ.c
é uma implementação clássica de uma fila priorizada
de mínimo
(= min-oriented priority queue).
Ela usa um
heap
pq[1..N]
organizado de modo que pq[1] tenha prioridade mínima.
(Infelizmente, a palavra mínima
é inconsistente com o significado usual
da palavra prioridade
.)
O código abaixo é uma adaptação do programa 9.12
do volume 1 do livro de Sedgewick.
/* Este módulo implementa uma fila priorizada em um heap. O heap é armazenado num vetor pq[1..N] de vértices. (A posição 0 do vetor não é usada.) */
#define vertex int static vertex *pq; static int N;
/* As prioridades são dadas em um vetor prty[] indexado por vértices: o vértice na posição k de pq[] tem prioridade prty[pq[k]]. O heap é caracterizado pela propriedade prty[pq[k/2]] <= prty[pq[k]] para k = 2,...,N. Portanto, o vértice pq[1] tem prioridade mínima. */
#define greater( i, j) (prty[pq[i]] > prty[pq[j]] ? 1 : 0)
/* O vetor qp[0..N-1] é o "inverso" de pq[]: para cada vértice v, qp[v] é o único índice tal que pq[qp[v]] == v. É claro que qp[pq[i]] == i para todo i. */
static int *qp; void PQinit( int maxN) { pq = malloc( (maxN+1) * sizeof (vertex)); qp = malloc( maxN * sizeof (int)); N = 0; }
/* Supõe-se que teremos sempre N <= maxN. */
int PQempty( void) { return N == 0; } void PQinsert( vertex v, int prty[]) { qp[v] = ++N; pq[N] = v; fixUp( N, prty); }
/* Retira da fila um vértice v que minimiza prty[v] e devolve v. */
vertex PQdelmin( int prty[]) { exch( 1, N); --N; fixDown( 1, prty); return pq[N+1]; }
/* Rearranja a fila depois que a prioridade prty[w] do vértice w diminuiu (e portanto w deve ser deslocada em direção ao início da fila). */
void PQdec( vertex w, int prty[]) { fixUp( qp[w], prty); } static void exch( int i, int j) { vertex t; t = pq[i]; pq[i] = pq[j]; pq[j] = t; qp[pq[i]] = i; qp[pq[j]] = j; } static void fixUp( int k, int prty[]) { while (k > 1 && greater( k/2, k)) { exch( k/2, k); k = k/2; } } static void fixDown( int k, int prty[]) { int j; while (2*k <= N) { j = 2*k; if (j < N && greater( j, j+1)) j++; if (!greater( k, j)) break; exch( k, j); k = j; } } void PQfree( ) { free( pq); free( qp); }
Estimativa do consumo de tempo no pior caso de cada uma das funções: