heap.java

Clustering demo.very good

class Heap{
   private Node[] heapArray;
   private int maxSize;            // size of array
   private int currentSize;       // number of nodes in array

   public Heap(int mx){         // constructor
      maxSize = mx;
      currentSize = 0;
      heapArray = new Node[maxSize];  // create array
   }

   public boolean isEmpty(){ 
      return currentSize==0; 
   }

   public boolean insert(double key,String name){
      if(currentSize==maxSize)
         return false;
      Node newNode = new Node(key, name);
      heapArray[currentSize] = newNode;
      trickleUp(currentSize++);
      return true;
   } 

   public void trickleUp(int index){
      int parent = ( index-1) / 2;
      Node bottom = heapArray[index];
         while( index > 0 && heapArray[parent].getKey() > bottom.getKey()){
             heapArray[index] = heapArray[parent];  // move it down
             index = parent;
             parent = (parent-1) / 2;
         } 
      heapArray[index] = bottom;
  }

   public String getRootElement(){           // delete item with max key
      Node root = heapArray[0];
      System.out.println("CurSize is "+currentSize);
      heapArray[0] = heapArray[--currentSize];
      System.out.println("Root is "+root.getKey()+" Cluster Name is: "+root.getClusterName());
      System.out.println("CurSize is "+currentSize);
      trickleDown(0);
      return root.getClusterName();
   }  

   public void remove(String name){//, Double dist){
	int i,f;
//	System.out.println("name is : "+name+"dist is: "+dist);
       for( i=0,f=0; i<currentSize;i++){
	if(f==0 && name.equals("cluster18")){
	      for(int j=0;j<currentSize;j++)
	           System.out.println("heap[j] is "+heapArray[j].getClusterName()+"key is: "+heapArray[j].getKey());
	      f=1;
	}
	if( heapArray[i].getClusterName().equals(name)){ // && heapArray[i].getKey()==dist ){
		heapArray[i]=heapArray[--currentSize];
		System.out.println("array size is: "+currentSize+" position of i to trickle down is: "+i+" name is: "+name);
		trickleDown(i);
		break;
	}
        } 
  }

   public void trickleDown(int index){
      int smallChild;
      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 smaller child
                       if(rightChild < currentSize &&  heapArray[rightChild].getKey() < heapArray[leftChild].getKey())
	            smallChild = rightChild;
	   else
	            smallChild = leftChild;
                                         // top <= smallChild?
                      if( top.getKey() <= heapArray[smallChild].getKey() )
	            break;
                                    // shift child up
               heapArray[index] = heapArray[smallChild];
               index = smallChild;            
          }
      heapArray[index] = top;            
  }  

   public boolean change(int index, int newValue){
        if(index<0 || index>=currentSize)
             return false;
        double oldValue = heapArray[index].getKey(); 
        heapArray[index].setKey(newValue);  
        if(oldValue < newValue)       
            trickleUp(index);                
       else                                
           trickleDown(index);        
       return true;
   }

   public void displayHeap(){
       System.out.print("heapArray: ");    
             for(int m=0; m<currentSize; m++)
                  if(heapArray[m] != null)
                       System.out.print( heapArray[m].getKey() + " ");
                  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].getKey()+"   "+heapArray[j].getClusterName());

         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
         }
      System.out.println("\n"+dots+dots); // dotted bottom line
  }
}