#ifndef _HEAP_H_
#define _HEAP_H_

#include "comum.h"

/*
  Heap.h
 
  Cabecalho para rotinas de heap com operacoes:
 
  cria heap
  destroi heap
  testa se vazio
  extrai minimo
  insere
  imprime
  
  Este heap e' generico, no sentido de que alem da chave inteira cada elemento pode guardar uma informacao generica, aqui representada como void *.  Na hora de usar, isto pode ser um apontador para qualquer outra coisa, e deve ser feito um "cast" na chamada.  Exemplo: quero guardar uma Arvore; entao:
 
  InsereOk(&h, (void *)Arvore);
 
  (supondo que o tipo Arvore seja um apontador).
 
  ATENCAO: o heap pode ter chaves repetidos. Nos casos onde houver empate para escolha entre filhos, selecionar SEMPRE o filho esquerdo.
 
*/

#define MAXTAMHEAP 500
 
typedef struct heap {
  int n;                        /* numero de elems no heap */
 
  /* para os vetores abaixo, sao validos os indices de 0 a n-1 */
 
  int chave[MAXTAMHEAP];        /* chave inteira dos itens */
  void *info[MAXTAMHEAP];    /* outras informacoes dos itens */
 
} Heap;

void CriaHeap (Heap *h);        /* faz n=0 */
 
void DestroiHeap (Heap *h);     /* faz n=-1 */
 
int VazioHeap (Heap *h);        /* 1 se vazio ou nao inicializado; */
                                /* 0 se nao vazio */
 
/* 1 se inseriu ok, 0 se deu algum problema */
 
int InsereOk (Heap *h, int chave, void *info);
 
/* 1 se extraiu ok, 0 se deu algum problema */
 
int ExtraiMinOk (Heap *h, int *chave, void **info);  

/* imprime so' as chaves do heap, na ordem por profundidade */
/* (raiz, filho esquerdo da raiz, filho direito da raiz, */
/* filho esquerdo do filho esquerod da raiz, ...) */
 
void ImprimeChaves (Heap h);                       

#endif