// Este arquivo: PQ.h
// Data: 2019-10-28
// Digitador: Paulo Feofiloff
//
// Esta é a interface da implementação de uma fila priorizada "de mínimo"
// (= min-oriented priority queue) composta por de vértices de um grafo (veja
// GRAPHlists.h e GRAPHlists.c).
//
// O código é uma adaptação do programa 9.11, p.390, do livro "Algorithms",
// 3rd.ed., part 1, de Sedgewick.
////////////////////////////////////////////////////////////////////////////////


#ifndef _PQ_h
#define _PQ_h

#include "MYTOOLS.h" // mallocc()

// Os vértices (de grafos) são inteiros positivos (veja GRAPHlists.h).
#define vertex int

// As prioridades na fila são dadas em um vetor prty[] indexado por vértices.
// Quanto menor prty[v], mais próximo está v do início da fila. [Estamos usando
// a palavra "prioridade" de maneira contra-intuitiva.] Se v é o primeiro
// vértice da fila então prty[v] é mínimo.

void 
PQinit( int V);
// Supõe-se que a fila tem no máximo V vértices.

int 
PQempty( void);

void 
PQinsert( vertex v, int prty[]);

// Retira da fila um vértice v que minimiza prty[v] e devolve v.
vertex 
PQdelmin( int prty[]);

// 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[]);

void 
PQfree( );

#endif