ADTs de 1ª ordem: Fila de Prioridade

Interface

 #include "Item.h"
 
 void PQinit(int);
 int  PQempty();
 void PQinsert(Item);
 Item PQdelmax();

Implementação

Com Amontoado

 #include <stdlib.h>
 #include "Item.h" 
 
 static Item *pq; 
 static int N;

 void PQinit(int maxN) {
   pq = malloc((maxN+1)*sizeof(Item)); N = 0;
 }
 
 int  PQempty()        { return N == 0; }
 void PQinsert(Item v) { pq[++N] = v; fixUp(pq, N); }
 
 Item PQdelmax() { 
   exch(pq[1], pq[N]); 
   fixDown(pq, 1, N-1); 
   return pq[N--]; 
 }

Com Vector

 static Item *pq; 
 static int N;
 
 void PQinit(int maxN) {
   pq = malloc(maxN*sizeof(Item)); N = 0;
 }
 
 int  PQempty()        { return N == 0; }
 void PQinsert(Item v) { pq[N++] = v; }

 Item PQdelmax() {
   int j, max = 0;
   for (j = 1; j < N; j++)
     if (less(pq[max], pq[j])) max = j;
   exch(pq[max], pq[N-1]);  
   return pq[--N];
 }

Algoritmo de Ordenação

O algoritmo de ordenação com base em filas de prioridade é um exemplo de um cliente do ADT descrito acima. O princípio de funcionamento consiste na inserção dos elementos a ordenar na fila e depois removê-los ordenadamente.

 #include <stdlib.h>
 #include "Item.h"
 #include "PQ.h"

 void PQsort(Item a[], int l, int r) {
   int k;
   PQinit();
   for (k = l; k <= r; k++) PQinsert(a[k]);
   for (k = r; k >= l; k--) a[k] = PQdelmax();
 }