/* Algorithmen und Programmierung 3
Uebung 3
Aufgabe 21 a) und b)

Tobias Hermes, Axel Steinacker

Tutor: Till Zoppke

Das Interface analog zur Minimalanforderung auf der Uebungsblatt.
*/
import java.io.*;

interface PWSchlange
{   
	void einfuegen(Comparable c);
    	Comparable entferneMin(); 
    	boolean istleer();
} //PWSchlange



/* 
Die Klasse Halde (streng nach Zettel) als Implementierung analog zu seinem Pseudocode aus der VL
*/

public class Halde implements PWSchlange
{ 
    int n=0;        							// Länge 
    Comparable [] a;  						// Array als Ablage

    public Halde(int maxLaenge) 		// maximale Länge
    {
			a = new Comparable [maxLaenge+1]; 
    } //Konstruktor

    public Comparable entferneMin() 
    {   
			if (n<=0) return null; //Haldenunterlauf
    	Comparable c = a[1];			      							//Erstes Element festhalten
    	n--;
    	if (n>0) 				      												//noch Elemente vorhanden
    	{
      	a[1] = a[n+1];			    										//letztes Element verschieben
       	zugross(1);				     										  // Haldenordnung wiederherstellen
      } // if
    	return c;				      											  // erstes (kleinstes) Element ausgeben
    }// entferneMin    

    public void einfuegen(Comparable c)
    {   
		if (n>=a.length-1) return;
    	a[++n] = c; 																	//an letzter Pos. einfügen
    	zuklein(n);																		// Haldenordnung wiederherstellen
    } //einfügen  

    void zuklein(int i) 														// a[i] kann kleiner als der Vorgänger sein
    {   
			if (i==1) return;															//nur 1 Element ist nicht kleiner ;)
    	int Vorgaenger = i/2;													// Vorgänger in der Baumstruktur
    	if (a[i].compareTo(a[Vorgaenger])<0) 					// Vergleich mit Vorgänger ist echt kleiner
    	{
    		vertausche(i,Vorgaenger);										// -> Vertauschen der beiden Elemente
    	  zuklein(Vorgaenger);												// Haldenordnung wiederherstellen
    	} // if
    } //zuklein

    void zugross(int i) 															// a[i] kann auch gröîer als der Nachfolger sein
    {   
			int kleinsterNachfolger;
    	if (2*i+1 <= n) 															// Nachfolger 1 noch im Feld
    	{
    		if (a[2*i].compareTo(a[2*i+1])<0) kleinsterNachfolger = 2*i;
       	else                              kleinsterNachfolger = 2*i+1;
    	} // if
      else if (2*i <= n) kleinsterNachfolger = 2*i;  //Nachfolger 2 im Feld
      else return;
    	if (a[i].compareTo(a[kleinsterNachfolger]) >0) //Vergleich ist gröîer
    	{
      	vertausche(i, kleinsterNachfolger);					 // Vertauschen
       	zugross(kleinsterNachfolger);								 // Haldenordnung wiederherstellen
      } // if
    } //zugroß

    public boolean istleer() 
    {
    	return n==0;					
    }
    
    void vertausche(int d, int e)				
    { 
			Comparable c	=a[d]; 
			a[d]		=a[e]; 
			a[e]		=c; 		//klassischer Dreieckstausch
    }//istLeer
} // Halde
