/*
 * Heap de máximo
 */

#include <stdlib.h>
#include <stdio.h>
#include "heap.h"

int pai(int i) { return (i-1)/2; }
int esq(int i) { return 2*i + 1; }
int dir(int i) { return 2*i + 2; }

int existe_pai(int i) { return i > 0; }
int existe_esq(int i, int n) { return esq(i) < n; }
int existe_dir(int i, int n) { return dir(i) < n; }

void cria(Heap *heap, int max_n) {
  heap->h = malloc (max_n * sizeof(int));
  heap->max_n = max_n;
  heap->n = 0;
}

void destroi(Heap *heap) {
  free(heap->h);
}

int verifica(Heap *heap) {
  int i;
  for (i = heap->n-1; existe_pai(i); i--)
    if (heap->h[i] > heap->h[pai(i)])
      return 0;
  return 1;
}

/* Retorna 0 caso o heap já esteja cheio. */
int insere(Heap *heap, int v) {
  if (heap->n == heap->max_n)
    return 0;
  int i = heap->n; 
  while (existe_pai(i) &&
	 heap->h[pai(i)] < v) {
    heap->h[i] = heap->h[pai(i)];
    i = pai(i);
  }
  heap->h[i] = v;
  heap->n++;
  return 1;
}

/* Retorna o elemento máximo do heap ou -1
   caso o heap esteja vazio. */
int remove_max(Heap *heap, int *m) {
  if (heap->n == 0)
    return 0;
  *m = heap->h[0];
  heap->n--;
  if (heap->n != 0) {
    int i = 0;
    int v = heap->h[heap->n];
    while(existe_esq(i, heap->n)) {
      int j = esq(i);
      if (existe_dir(i, heap->n) &&
	  heap->h[dir(i)] > heap->h[esq(i)])
	j = dir(i);
      if (v > heap->h[j])
	break;
      heap->h[i] = heap->h[j];
      i = j;
    }
    heap->h[i] = v;
  }
  return 1;  
}



int main() {
  Heap heap;

  cria(&heap, 12);
  insere(&heap, 10);
  insere(&heap, 3);
  insere(&heap, 15);
  insere(&heap, 11);
  insere(&heap, 14);    
  verifica(&heap);

  int m;
  while (remove_max(&heap, &m)) 
    if (verifica(&heap))
      printf("%d\n", m);

  return 0;
}