Unit 9 Chapter 12 Heaps Code

Question 1

heap

Answer 1

////////////////////////////////////////////////////////////////
class Node
   {
   private int iData;             // data item (key)
// -------------------------------------------------------------
   public Node(int key)           // constructor
      { iData = key; }
// -------------------------------------------------------------
   public int getKey()
      { return iData; }
// -------------------------------------------------------------
   public void setKey(int id)
      { iData = id; }
// -------------------------------------------------------------
   }  // end class Node
////////////////////////////////////////////////////////////////
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(int key)
      {
      if(currentSize==maxSize)
         return false;
      Node newNode = new Node(key);
      heapArray[currentSize] = newNode;
      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].getKey() > bottom.getKey() )
     {
     heapArray[index] = heapArray[parent];  // move it down
     index = parent;
     parent = (parent-1) / 2;
     }  // end while
  heapArray[index] = bottom;
  }  // end trickleUp() // -------------------------------------------------------------    public Node remove()           // delete item with max key
  {                           // (assumes non-empty list)
  Node root = heapArray[0];
  heapArray[0] = heapArray[--currentSize];
  trickleDown(0);
  return root;
  }  // end remove() // -------------------------------------------------------------    public void trickleDown(int index)
  {
  int largerChild;
  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].getKey() <
                         heapArray[rightChild].getKey())
        largerChild = rightChild;
     else
        largerChild = leftChild;
                                     // top >= largerChild?
     if( top.getKey() =currentSize)
     return false;
  int oldValue = heapArray[index].getKey(); // remember old
  heapArray[index].setKey(newValue);  // change to new

      if(oldValue < newValue)             // if raised,
         trickleUp(index);                // trickle it up
      else                                // if lowered,
         trickleDown(index);              // trickle it down
      return true;
      }  // end change()
// -------------------------------------------------------------
   public void displayHeap()
      {
      System.out.print("heapArray: ");    // array format
      for(int m=0; m 0)              // for each heap item
         {
         if(column == 0)                  // first item in row?
            for(int k=0; k);
            }  // 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
////////////////////////////////////////////////////////////////