// Este arquivo: maxPQ.h
// Data: 2019-10-28
// Digitador: Paulo Feofiloff
//
// Esta é a interface da implementação de uma fila priorizada "de máximo"
// (= max-oriented priority queue) composta por 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 _maxPQ_h
#define _maxPQ_h

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

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

// As prioridades da fila são dadas em um vetor prty[] indexado por vértices.
// (O vetor é fornecido pelo usuário.) Se prty[v] > prty[w] então o vértice v
// tem prioridade maior que o vértice w. O vértice da fila que tem prioridade
// máxima é o primeiro a sair da fila.

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

int 
maxPQempty( void);

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

// Devolve um vértice v da fila que maximiza prty[v]. Esse vértice é retirado da
// fila.
vertex 
maxPQdelmax( int prty[]);

// Rearranja a fila depois que prty[w] aumentou (portanto move w em direção ao
// início da fila).
void 
maxPQinc( vertex w, int prty[]);

void 
maxPQfree( );

#endif