//////////////////////////////////////////////////////////
// CODE DI PRIORITA' - HEAP (creazione e procedure)	//
// AUTORE: Agnese Farinelli				//
// DATA: 3. marzo 2009					//
//////////////////////////////////////////////////////////

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

#define MAXLUNG 10
typedef int tipoelem;
typedef int boolean;

// Creo la struttura PRIORICODA.
// heap[MAXLUNG] = vettore heap
// ultimo = ultimo elemento di heap
struct prioricoda_struct {
  tipoelem heap[MAXLUNG];
  int ultimo;
};

typedef struct prioricoda_struct * prioricoda;

// Funzione CREAPRIORICODA
// Creo una nuova coda di priorità.
prioricoda CREAPRIORICODA(){
  prioricoda C;
  C = (prioricoda) malloc(sizeof(struct prioricoda_struct));	// alloco lo spazio necessario per la struttura prioricoda_struct
  C->ultimo = -1;						// l'ultimo elemento della coda è il nodo radice
  
  return C;
}

// Funzione MIN
// Restituisce il valore memorizzato nella radice.
tipoelem MIN(prioricoda C){
  if (C->ultimo > -1)
    return C->heap[0];
  else
    printf("ERRORE: heap vuoto!\n");
}

// Procedura CANCELLAMIN
// Cancello l'ultimo elemento dalla coda di priorità
void CANCELLAMIN(prioricoda C){

  boolean scambio;
  int i, k, n;
  
  if (C->ultimo == -1)
    printf("ERRORE: coda di priorità vuota!\n");
  else
    C->heap[0] = C->heap[C->ultimo];	// Inserisco nella radice l'ultimo valore di heap
    C->ultimo = C->ultimo - 1;		// Decremento il valore dell'ultimo elemento di heap
    i = 0;
    scambio = 1;
    n = C->ultimo + 1;			// numero di elementi del vettore heap
    
    while ((i < n/2) && scambio) {	// fino a che i = indice dei nodi non foglia
      k = (2 * i) + 1;			
      
      if (k < C->ultimo){
	if (C->heap[k] > C->heap[k + 1])
	  k = k + 1;
	else
	  k = k;
      }
      
      if (C->heap[k] < C->heap[i]){
	scambia(C->heap[k], C->heap[i]);
	i = k;
      }
      else
	scambio = 0;
    }
}

// Procedura INSERISCI
// Inserisce un nuovo elemento nella coda di priorità
void INSERISCI(tipoelem x, prioricoda C){
 
  int i, k;
  tipoelem tmp;
  
  if (C->ultimo = MAXLUNG -1)
    printf("ERRORE: coda di priorità piena!\n");
  else{
    C->ultimo = C->ultimo+ 1;
    C->heap[C->ultimo] = x;		// Inserisco l'elemento
    i = C->ultimo;
  
    if (i > 0)				// Se i non è nodo radice
      k = (i -1)/2;			// Indice del padre
            
    while ((i > 0) && (C->heap[i] < C->heap[k])){  // se non è un heap scambio
      scambia(C->heap[i], C->heap[k]);
      i = k;
    if (i > 0)
      k = (i - 1)/2; 			// indice del padre
    }
  }
}