class MyPriorityQueue
{
   //binaerer Heap soll auf Basis eines 
   //Arrays implementiert werden
   private PQEntry[] heap;
   //aktuelle Anzahl von Eintraegen
   private int heapsize;

   //Operation MakePQueue()
   public MyPriorityQueue(int maxheapsize)
   {
      heap = new PQEntry[maxheapsize];
      heapsize = 0;
   }

   public boolean isEmpty()
   {
      if(heapsize == 0) {return true;}
      else {return false;}
   }

   public void insert(String s,int p)
   {
      if(heapsize < heap.length)
      {
         //neues Element am Ende des Heaps einfuegen
         heap[heapsize] = new PQEntry(s,p);
         heapsize++;

         //Heapeigenschaft wieder herstellen
         int index = (heapsize-1);
         boolean heapnotokay = true;
         while(heapnotokay)
         {
            if(index == 0) {heapnotokay = false;}
            else
            {
               if(heap[index].p > heap[(index-1)/2].p)
               {
                  PQEntry e = heap[index];
                  heap[index] = heap[(index-1)/2];
                  heap[(index-1)/2] = e;
                  index = (index-1)/2;
               }
               else {heapnotokay = false;}
            }
         } 
      }
      else {System.out.println("Heap voll");}
   }

   public String removeMax()
   {
      String data = null;

      if(heapsize > 0)
      {
         data = heap[0].d;
 
         //letztes Element kommt in die Wurzel
         heapsize--;
         heap[0] = heap[heapsize];
      
         //Heapeigenschaft wieder herstellen
         int index = 0;
         boolean heapnotokay = true;
         while(heapnotokay)
         { 
            int l = 2*index + 1;
            int r = 2*index + 2;
            int indmaxp = index;
          
            if((l < heapsize) && (heap[l].p > heap[indmaxp].p)) {indmaxp = l;}
            if((r < heapsize) && (heap[r].p > heap[indmaxp].p)) {indmaxp = r;}

            if(indmaxp != index)
            {
               PQEntry e = heap[index];
               heap[index] = heap[indmaxp];
               heap[indmaxp] = e;
               index = indmaxp;
            }
            else {heapnotokay = false;}
         }
      }
      else {System.out.println("Heap leer");}
         
      return data;
   }

   //Ausgabe der Einträe im Heap -- zum Testen
   public void dumpHeap()
   {
      System.out.println("Heapsize: " + heapsize);

      for(int i = 0; i < heapsize; i++)
      {
         System.out.println(heap[i].d);
      }
   }
}