Filas de Prioridade
-------------------


Dado um conjunto C com uma relação de ordem linear sobre seus elementos,
considerar o problema de manter C com as seguintes operações:

1) Insere(C, x): Insere um novo elemento x em C;
2) RemoveMax(C): Retorna e remove o elemento com maior prioridade de C.

Representações possíveis:

a) Manter uma lista linear ligada em que os elementos estão armazenados
em ordem decrescente de prioridade
  - remover o elemento de maior prioridade -> rápido
  - inserir um novo elemento -> lento (pode-se percorrer toda a lista...)


b) Heap - Estrutura que se armazenada em um vetor tem as seguintes
 propriedades (supõe-se que a primeira posição do vetor é a 1):
  - O elemento na posição 1 é o maior (prioridade);
  - O elemento na posição k é maior do que os elementos nas posições
       2*k e 2*k+1 (se estas estiverem ocupadas)

  Exemplo:
     1  2  3  4  5  6  7  8  9 10 
    30|10|25| 8| 6|13|20| 4| 7| 5|

    Inserir o 11:
     1  2  3  4  5  6  7  8  9 10 11  // passo 1
    30|10|25| 8| 6|13|20| 4| 7| 5|11  // inserção ao final
                                  ^^

     1  2  3  4  5  6  7  8  9 10 11  // passo 2
    30|10|25| 8|11|13|20| 4| 7| 5| 6  // troca com o pai da pos 11 (no caso o 6)
                ^^                ^^

     1  2  3  4  5  6  7  8  9 10 11  // passo 3
    30|11|25| 8|10|13|20| 4| 7| 5| 6  // troca com o pai da pos 5 (no caso o 10)
       ^^       ^^

    Remover o 30:
     1  2  3  4  5  6  7  8  9 10 11  // passo 1
      |11|25| 8|10|13|20| 4| 7| 5| 6  // remove o 30
    ^^

     1  2  3  4  5  6  7  8  9 10 11  // passo 2
     6|11|25| 8|10|13|20| 4| 7| 5|    // coloco o último na posição
    ^^

     1  2  3  4  5  6  7  8  9 10 11  // passo 3
    25|11| 6| 8|10|13|20| 4| 7| 5|    // troco pelo maior (entre os filhos)
    ^^    ^^                          // se for o caso

     1  2  3  4  5  6  7  8  9 10 11  // passo 4
    25|11|20| 8|10|13| 6| 4| 7| 5|    // troco pelo maior (entre os filhos)
          ^^          ^^              // se for o caso
 
Algoritmo de Inserção:
#define MAX ...

typedef struct {
	int nelem;
        int vetor[MAX];
} heap;

void Insere(heap *h, int x) {
    int filho; 

    filho = ++h->nelem;   // última posição
    while (filho > 1 && x > h->vetor[filho/2]) {
         h->vetor[filho] = h->vetor[filho/2]; 
	 filho = filho / 2;
    }
    h->vetor[filho] = x;
}
    

Alocação dinâmica: eliminação de nós.
-------------------------------------

  Quando nós removemos um elemento de uma lista ligada, não queremos
  simplemente deixar aquele nó "perdido" na memória. Podemos
  devolvê-lo para a memória disponível através do comando free.

  Se vamos precisar criar novos nós, pode ser interessante guardar
  os nós descartados em uma lista, chamada de "lista livre".
  Isso economiza chamadas às funções malloc e free.

  Sempre que o programa necessita de um novo nó, o primeiro nó da
  lista livre é removido e utilizado. Sempre que um nó não é mais
  necessário, ele deve ser inserido na lista livre.


  typedef ... TipoInfo;
  typedef struct no1{
        TipoInfo   info;
        struct no1 *prox;
        } No, *apontNo;

  apontNo livre; /* conveniente que a lista livre seja global */


  void InicializaListaLivre() {
  livre = NULL;
  }


  void ExtraiNo(apontNo *p){
    if (livre == NULL) { 
       *p = (No *)malloc(sizeof(No));
       if( *p == NULL )
         Overflow();
    }
    else {
      *p    = livre;
      livre = livre->prox;
    }
  }

  void DevolveNo(apontNo p) {
    p->prox = livre;
    livre   = p; 
  }




    Listas Lineares Ligadas
    -----------------------


(1) Manipulação de uma Pilha

apontNo topo; 

void InicializaPilha() {
  topo = NULL;
}

void Empilha( TipoInfo x ) {
  apontNo p;

  ExtraiNo(&p);
  p->info = x;
  p->prox = topo;
  topo = p;
}

void Desempilha( TipoInfo *x ) {
  apontNo p;

  if( topo == NULL )
    Underflow();
  else {
    p  = topo;
    *x = p->info;
    topo = topo->prox;
    DevolveNo(p);
  }
}
 

(2) Manipulação de uma Fila em Lista Ligada 

   ___     ___     ___     ___
  |_|_|-> |_|_|-> |_|_|-> |_|_|-|
    î                       î   ~
  inicio                   fim


apontNo inicio, fim;

void InicializaFila() {
  inicio = fim = NULL;
}

void InsereFila( TipoInfo x ) {
  apontNo p;

  ExtraiNo(&p);
  p->info = x;
  p->prox = NULL;

  if( fim == NULL )
    inicio = p;
  else
    fim->prox = p;
  fim = p;  
}

void RemoveFila( TipoInfo *x ) {
  apontNo p;
  
  if( inicio == NULL )
    Underflow();
  else {
    p = inicio;
    *x = p->info;
    inicio = inicio->prox;
    if( inicio == NULL )
      fim = NULL;
    DevolveNo(p);
  }
}