/* =============================================================================
   Implementações de uma fila de prioridades.
   ========================================================================== */
#include "filaprio.h"

void SobeHeap(int *a, int *hvert, int *pos, int m){
  int x,y,j;
  x=a[m]; j=m/2; y=hvert[m]; 
  while ((j>=1) && (a[j]>x)) {
    a[m]=a[j]; 
    hvert[m]=hvert[j];
    pos[hvert[m]]=m;
    m=j;
    j=j/2;
  }
  a[m]=x;
  hvert[m]=y;
  pos[hvert[m]]=m;
  return;
}


void DesceHeap(int *a,int tamheap, int *hvert, int *pos, int m){
  int x,y,k; Boolean continua; 
  x=a[m]; y=hvert[m]; continua=true; k=2*m;
  while ((continua==true) && (k<=tamheap)) {
    if (k<tamheap) 
      if (a[k]>a[k+1]) 
        k++;
    if (x>a[k]) {
      a[m]=a[k];
      hvert[m]=hvert[k];
      pos[hvert[m]]=m;
      m=k;
      k=2*k;
    }
    else continua=false;
  }
  a[m]=x;
  hvert[m]=y;
  pos[hvert[m]]=m;
}


void RemoveHeap(int *a, int *hvert, int *pos, int *tamheap){
  int aux2=1;
  a[1]=a[*tamheap]; pos[hvert[1]]=-1; hvert[1]=hvert[*tamheap];
  (*tamheap)--;
  pos[hvert[1]]=1;
  DesceHeap(a,*tamheap,hvert,pos,aux2);
  return;
}

void ImprimeHeap(int n, int *dist, int *pred, int *pos, int nc){
  int i;

  printf("\n\n     i dist vert  pos\n");  
  for(i=1;i<=n;i++) printf("%6d %4d %4d %4d\n",i,dist[i],pred[i],pos[i]);
  printf("tam. heap=%d \n\n",nc);
  return;
} 
 

  

/* author: Gustavo Sverzut Barbieri (http://www.gustavobarbieri.com.br) */