// heap.java
// demonstrates heaps
// to run this program: C>java HeapApp
import java.io.*;
import java.util.*;
////////////////////////////////////////////////////////////////
class Node
   {
	private int identity; 
	private int parent;
	private double priority;             // weight
   
// -------------------------------------------------------------
   public Node(double pri, int id, int par)           // constructor
      { 
	   priority = pri;
	   identity = id;
	   parent = par;
      	}
// -------------------------------------------------------------
   public int getIdentity()
   { return identity; }
// -------------------------------------------------------------
   public double getPriority()
      { return priority; }
// -------------------------------------------------------------
   public void setPriority(double p)
      { priority = p; }
// -------------------------------------------------------------
   public int getParent()
   	  { return parent; }
//-------------------------------------------------------------
public void setParent(int p)
      { parent = p; }
//-------------------------------------------------------------
   }  // end class Node
////////////////////////////////////////////////////////////////
class VertexHeap
   {
   private Node[] heapArray;
   private int maxSize;           // size of array
   private int currentSize;       // number of nodes in array
   private int[] map;
// -------------------------------------------------------------
   public VertexHeap(int mx)            // constructor
      {
      maxSize = mx;
      currentSize = 0;
      heapArray = new Node[maxSize];  // create array
      //create map array
      map = new int[maxSize];
      for(int i = 0; i < map.length; i++)
    	  map[i] = -1;
      }
// -------------------------------------------------------------
   public int getIndex( int identity )
   {
	   return map[identity];
   }
// -------------------------------------------------------------
   public boolean isEmpty()
      { return currentSize==0; }
// -------------------------------------------------------------
   public boolean insert(Node newNode)
      {
      if(currentSize==maxSize)
         return false;
      heapArray[currentSize] = newNode;
      map[newNode.getIdentity()] = currentSize; //set position in heap 
      trickleUp(currentSize++);
      return true;
      }  // end insert()
// -------------------------------------------------------------
   public void trickleUp(int index)
      {
      int parent = (index-1) / 2;
      Node bottom = heapArray[index];
      
      while( index > 0 && heapArray[parent].getPriority() > bottom.getPriority() )
      {
         //swap( map, heapArray[index].getIdentity(), heapArray[parent].getIdentity() );
    	 swap( map, heapArray[index].getIdentity(), bottom.getIdentity());
         heapArray[index] = heapArray[parent];  // move it down  
         index = parent;
         parent = (parent-1) / 2;
      }  // end while
      swap( map, heapArray[index].getIdentity(), bottom.getIdentity());
      heapArray[index] = bottom;
      }  // end trickleUp()
// -------------------------------------------------------------
   public Node delete()           // delete item with max key
      {                           // (assumes non-empty list)
      Node root = heapArray[0];
      //for map
      map[heapArray[0].getIdentity()] = -1;
      map[heapArray[--currentSize].getIdentity()] = 0;
      //fix heap
      heapArray[0] = heapArray[currentSize];
      trickleDown(0);
      return root;
      }  // end remove()
// -------------------------------------------------------------
   public void trickleDown(int index)
      {
      int smallerChild = 0;
      Node top = heapArray[index];       // save root
      while(index < currentSize/2)       // while node has at
         {                               //    least one child,
         int leftChild = 2*index+1;
         int rightChild = leftChild+1;
                                         // find larger child
         if(rightChild < currentSize &&  // (rightChild exists?)
                             heapArray[leftChild].getPriority() >
                             heapArray[rightChild].getPriority())
            smallerChild = rightChild;
         else
            smallerChild = leftChild;
         
         // top >= smallerChild?
         if( top.getPriority() <= heapArray[smallerChild].getPriority() )
            break;
         
         // shift child up & fix map
         swap( map, heapArray[smallerChild].getIdentity(), top.getIdentity());
         heapArray[index] = heapArray[smallerChild];
         index = smallerChild;            // go down
         
      }  // end while
      heapArray[index] = top;            // root to index
      }  // end trickleDown()
// -------------------------------------------------------------
   public boolean change(int index, double newPriority, int parent)
      {
      if(index<0 || index>=currentSize)
         return false;
      double oldValue = heapArray[index].getPriority(); // remember old
      
      //only change if lower, this is needed for our myWeightedGraph class
      if( oldValue < newPriority)
    	  return false;
      
      heapArray[index].setPriority(newPriority);  // change to new
      heapArray[index].setParent( parent );

      trickleDown(index);              // trickle it down
      return true;
      }  // end change()
// -------------------------------------------------------------
   public void displayHeap()
      {
      System.out.print("heapArray: ");    // array format
      for(int m=0; m<currentSize; m++)
         if(heapArray[m] != null)
            System.out.print( heapArray[m].getIdentity() + " ");
         else
            System.out.print( "-- ");
      System.out.println();
                                          // heap format
      int nBlanks = 32;
      int itemsPerRow = 1;
      int column = 0;
      int j = 0;                          // current item
      String dots = "...............................";
      System.out.println(dots+dots);      // dotted top line

      while(currentSize > 0)              // for each heap item
         {
         if(column == 0)                  // first item in row?
            for(int k=0; k<nBlanks; k++)  // preceding blanks
               System.out.print(' ');
                                          // display item
         System.out.print(heapArray[j].getPriority());

         if(++j == currentSize)           // done?
            break;

         if(++column==itemsPerRow)        // end of row?
            {
            nBlanks /= 2;                 // half the blanks
            itemsPerRow *= 2;             // twice the items
            column = 0;                   // start over on
            System.out.println();         //    new row
            }
         else                             // next item on row
            for(int k=0; k<nBlanks*2-2; k++)
               System.out.print(' ');     // interim blanks
         }  // end for
      System.out.println("\n"+dots+dots); // dotted bottom line
      }  // end displayHeap()
// -------------------------------------------------------------
   public void swap( int[] array, int a, int b)
   {
	  int temp = array[a];
	  array[a] = array[b];
	  array[b] = temp;
	  return;
   }
// -------------------------------------------------------------
   }  // end class Heap
////////////////////////////////////////////////////////////////
class HeapApp
   {
   public static void main(String[] args) throws IOException
      {
      int value, value2;
      VertexHeap theHeap = new VertexHeap(31);  // make a Heap; max size 31
      boolean success;

      theHeap.insert(new Node(70, 1, 0));           // insert 10 items
      theHeap.insert(new Node(40, 2, 0));
      theHeap.insert(new Node(50, 3, 0));
      theHeap.insert(new Node(20, 4, 0));
      theHeap.insert(new Node(60, 5, 0));
      theHeap.insert(new Node(100, 6, 0));
      theHeap.insert(new Node(80, 7, 0));
      theHeap.insert(new Node(30, 8, 0));
      theHeap.insert(new Node(10, 9, 0));
      theHeap.insert(new Node(90, 10, 0));

      while(true)                   // until [Ctrl]-[C]
         {
         System.out.print("Enter first letter of ");
         System.out.print("show, insert, delete, getIndex, change: ");
         int choice = getChar();
         switch(choice)
            {
            case 's':                        // show
               theHeap.displayHeap();
               break;
            case 'i':                        // insert
               System.out.print("Enter value to insert: ");
               value = getInt();
               success = theHeap.insert(new Node(value, 0, 0) );
               if( !success )
                  System.out.println("Can't insert; heap full");
               break;
            case 'd':                        // remove
               if( !theHeap.isEmpty() )
                  theHeap.delete();
               else
                  System.out.println("Can't delete; heap empty");
               break;
            case 'g': 
               System.out.print("Enter current identity of item: ");
               value = getInt();
               System.out.println( "Index is: " + theHeap.getIndex(value));
               break;   
            case 'c':                        // change
               System.out.print("Enter current index of item: ");
               value = getInt();
               System.out.print("Enter new key: ");
               value2 = getInt();
               success = theHeap.change(value, value2, 0);
               if( !success )
                  System.out.println("Invalid index");
               break;
            default:
               System.out.println("Invalid entry\n");
            }  // end switch
         }  // end while
      }  // end main()
//-------------------------------------------------------------
   public static String getString() throws IOException
      {
      InputStreamReader isr = new InputStreamReader(System.in);
      BufferedReader br = new BufferedReader(isr);
      String s = br.readLine();
      return s;
      }
//-------------------------------------------------------------
   public static char getChar() throws IOException
      {
      String s = getString();
      return s.charAt(0);
      }
//-------------------------------------------------------------
   public static int getInt() throws IOException
      {
      String s = getString();
      return Integer.parseInt(s);
      }
//-------------------------------------------------------------
  }  // end class HeapApp
////////////////////////////////////////////////////////////////