View source for 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'''();
  }