import java.util.Comparator;

/**
 * Clase para crear y trabajar colas de prioridad utilizando heaps.
 * @author  Amparo Lopez Gaona.
 * @version 1a. ed.
 */
class Heap implements EncolableConPrioridad{
    private Object [] elementos;   // Arreglo en donde se guarda la cola
    private int nElementos ;       // Cantidad de elementos almacenados
    private Comparator cmp;        // Comparador para los elementos

  /**
   * Constructor que recibe un comparador
   * @param Comparator -- comparador para la prioridad de los elementos
   */
    public Heap (Comparator c) { 
	this(c, 100);
    }

  /**
   * Constructor que recibe un comparador y el tamano máximo del heap
   * @param Comparator -- comparador para la prioridad de los elementos
   * @param int -- tamano máximo del heap
   */
    public Heap(Comparator c, int tam) {
	cmp = c;
	elementos = new Object[(tam > 0) ? tam : 100];
	nElementos = 0;
    }

  /**
   * Constructor que crea una cola de prioridad a partir de un arreglo
   * @param Comparator -- comparador para la prioridad de los elementos
   * @param Object [] -- arreglo de objetos que formarán el heap.
   */
    public Heap(Comparator c, Object [] datos) {
	nElementos = 0;
	elementos = new Object[datos.length*2];
	cmp = c;

	for (int i = 0; i < datos.length; i++)
	    agregar(datos[i]);
    }

  /**
   * Constructor de copia
   * @param Heap -- heap del cual se creará una copia
   */
  public Heap(Heap hep) {
    nElementos = hep.nElementos;
    elementos = new Object[nElementos];
    cmp = hep.cmp;
    for (int i = 0; i < nElementos; i++)
      elementos[i] = hep.elementos[i];
  }

  /**
   * Método para determinar si la cola de prioridad está vacía
   * @return boolean -- Devuelve true si la cola está vacía y false en
   *                    otro caso
   */
    public boolean estaVacia() { 
	return 	nElementos == 0;
    }

  /**
   *  Método para eliminar todos los elementos de la cola de prioridad.  
   */
    public void vaciar() {
	nElementos = 0;
    }

  /** 
   * Método para conocer la cantidad de elementos que tiene la cola 
   * de prioridad.
   * @return int -- número de elementos en la cola de prioridad
   */
    public int tamanio() { 
	return 	nElementos;
    }

  /**
   *  Método para obtener el primer elemento de la cola de prioridad
   * @return Object -- el primer elemento en la cola de prioridad
   */
    public Object obtenerPrimero() {  
	return elementos[0];
    }

  /**
   * Metodo para agregar un nuevo elemento en la cola de prioridad
   * @param valor -- Objeto que se va a insertar
   */
    public void agregar(Object valor) { 
	int posicion = nElementos; // Va agregar el dato al final
        int posPadre = (nElementos -1)/2;
	Object valorPadre = null;  

	if (posicion == elementos.length) crecerArreglo();

	elementos[posicion] = valor;
	if (posPadre >=0)
	    valorPadre = elementos[posPadre];
	while((posicion > 0) && (cmp.compare(valor, valorPadre) < 0)) {
	    elementos[posicion] = valorPadre;
	    posicion = posPadre;
	    posPadre = (posicion -1)/2;
	    if (posPadre >= 0)
		valorPadre = elementos[posPadre];
	}
	elementos[posicion] = valor;
	nElementos++;
    }

    private void crecerArreglo() {
	System.out.println("Voy a aumentar el tamano del arreglo");
	Object [] tmp = new Object[elementos.length+10];
	for (int i = 0; i < elementos.length; i++)
	    tmp[i] = elementos[i];
	elementos = tmp;
    }

  /** Metodo para eliminar el elemento de menor prioridad
   */
    public void eliminar() {        //YA
	int ultimaPos = tamanio() - 1;

	if (ultimaPos != 0)    // Elimina el primer elemento
	    elementos[0] = elementos[ultimaPos];//[elementos]];

	nElementos--;  // Elimina el ultimo elemento
	ajustarHeap(0, nElementos);
    }

/*
 * Método privado para ajustar un heap
 * @param pos -- posición del nodo a partir del cual va a verificar que
 *               se tenga un heap
 * @param tamano -- tamanio del arreglo 
 */
    private void ajustarHeap(int pos, int tamano) {      //YA
	Object valor = elementos[pos];
	while (pos < tamano) {
	    int posHijo = pos *2 + 1;
	    if (posHijo < tamano) {
		if (((posHijo + 1) < tamano) && 
		    cmp.compare(elementos[posHijo+1], elementos[posHijo]) <0)
		    posHijo++;
		if (cmp.compare(valor, elementos[posHijo]) < 0) {
		    elementos[pos] = valor;
		    return;
		} else {
		    elementos[pos] = elementos[posHijo];
		    pos = posHijo;
		}
	    } else {
		elementos[pos] = valor;
		return;
	    }
	}
    }

/**
 * Método para ordenar utilizando el algoritmo heapsort
 * @return Object[] -- arreglo con los objetos ordenados.
 */
    public Object[] ordenar() {
	Object [] ordenados = new Object[nElementos];
	Heap copia = new Heap (this);

	for (int i = 0; i < ordenados.length; i++) {
	    ordenados[i] = copia.obtenerPrimero();
	    copia.eliminar();
	}

	return ordenados;
    }
}