Binary Trees, Heaps, and HeapSort

(see also the C++ version)

import java.io.*;
import java.util.*;

/***--------------------------------------------------------------------***/
/***  In this example we will be interested in storing integer objects  ***/
/***--------------------------------------------------------------------***/
class BigInt
{
   int number;

   BigInt(int x)  { number = x; }
   int value()    { return number; }
   void display() { System.out.print(number + " "); }
}

/***--------------------------------------------------------------------***/
/***   The Cell class is used to "carry" the objects in the HeapSort    ***/
/***--------------------------------------------------------------------***/
class Cell
{
   Object item;
   Cell leftnext;
   Cell rghtnext;
   Cell lefttree;
   Cell rghttree;
   Cell parent;

   Cell(Object data, Cell ln, Cell prnt)
   {
      item     = data;
      lefttree = null;
      rghttree = null;
      leftnext = ln;
      rghtnext = null;
      parent   = prnt;
   }
   Object objectOf()     { return item; }
   Cell   parentOf()     { return parent; }
   Cell   leftChildOf()  { return lefttree; }
   Cell   rightChildOf() { return rghttree; }
   Cell   leftNextOf()   { return leftnext; }
   Cell   rightNextOf()  { return rghtnext; }
   void   setLeftChild(Cell t)  { lefttree = t; }
   void   setRightChild(Cell t) { rghttree = t; }
   void   setLeftNext(Cell t)   { leftnext = t; }
   void   setRightNext(Cell t)  { rghtnext = t; }
   void   setObject(Object obj) { item = obj; }
}

/***--------------------------------------------------------------------***/
/***  The class of Binary Trees -                                       ***/
/***    includes the following methods, among others                    ***/
/***       1. HeapifyDown - percolate an object down from the root      ***/
/***       2. HeapifyUp   - percolate an object up from a leaf          ***/
/***       3. popNode     - delete the last Cell and return its object  ***/
/***       4. setRoot     - replace an object at the root with another  ***/
/***       5. HeapSort    - repeat: setRoot(popNode()); heapifyDown();  ***/
/***       6. addNodeToHeap - add a Cell to end of heap and add object  ***/
/***    saves information in the following variables                    ***/
/***       1. dispfn      - pointer to function that displays the tree  ***/
/***       2. valfn       - pointer to function returning value of obj  ***/
/***       3. head, tail  - pointers locating root and end of tree      ***/
/***    tail pointer -                                                  ***/
/***       1. points to a leaf Cell if the tree has an odd number of    ***/
/***          Cells.  If the tree has one cell, it points to the root,  ***/
/***          otherwise it points to the leftmost Cell in the row that  ***/
/***          is one up from the bottom that has no children, or, in    ***/
/***          the case of a full tree, it points to the leftmost Cell   ***/
/***          of the bottom level.                                      ***/
/***       2. points to the rightmost Cell, one level up from the       ***/
/***          bottom, that has a child.                                 ***/
/***--------------------------------------------------------------------***/
class BinTree
{
   Cell head;
   Cell tail;

   /***--------------------------------------------------------------------***/
   /***   This is the function used to return an object value for BigInt   ***/
   /***--------------------------------------------------------------------***/
   int valuefunc(Object obj)   { return ((BigInt)(obj)).value(); }

   BinTree() { head = tail = null;  }

   /***--------------------------------------------------------------------***/
   /***                   Basic function for building a heap               ***/
   /***--------------------------------------------------------------------***/
   void addNodeToHeap(Object obj)
   {
      addNode(obj);
      heapifyUp();
   }

   Object getRoot()
   {
      Object obj = head.objectOf();
      head.setObject(null);
      return obj;
   }

   /***--------------------------------------------------------------------***/
   /***       Remove the last Cell from a tree and return its object       ***/
   /***--------------------------------------------------------------------***/
   Object popNode()
   {
      if (head == null) return null;
      if (tail.leftNextOf() == null && tail.leftChildOf() == null)
      {
         Object obj = head.objectOf();
         head = tail = null;
         return obj;
      }
      else
      if (tail.leftChildOf() != null)
      {
         Object obj = tail.leftChildOf().objectOf();
         tail.leftChildOf().leftNextOf().setRightNext(null);
         tail.setLeftChild(null);
         return obj;
      }
      else
      {
         tail = tail.leftNextOf();
         Object obj = tail.rightChildOf().objectOf();
         tail.leftChildOf().setRightNext(null);
         tail.setRightChild(null);
         return obj;
      }
   }

   /***--------------------------------------------------------------------***/
   /***  Heapify Down -                                                    ***/
   /***     let t be a Cell with an object                                 ***/
   /***     let h be the child Cell of t with object of least value        ***/
   /***     if no such child Cell exists, stop                             ***/
   /***     otherwise, if t's object value > h's object value              ***/
   /***     then swap t's object with h's object, set t = h, and repeat    ***/
   /***--------------------------------------------------------------------***/
   void heapifyDown()
   {
      Cell t = head, h;
      Object obj;

      if (head == null) return;

      while (true)
      {
         if (t.leftChildOf() == null && t.rightChildOf() == null)
            break;
         else
         if (t.rightChildOf() == null)
             h = t.leftChildOf();
         else
         if (valuefunc(t.leftChildOf().objectOf())
              < valuefunc(t.rightChildOf().objectOf()))
            h = t.leftChildOf();
         else
            h = t.rightChildOf();

         if (valuefunc(h.objectOf()) < valuefunc(t.objectOf()))
         {
            obj = t.objectOf();
            t.setObject(h.objectOf());
            h.setObject(obj);
            t = h;
         }
         else
            break;
      }
   }

   /***--------------------------------------------------------------------***/
   /***  Heapify Up -                                                      ***/
   /***     let h be the last Cell of the tree                             ***/
   /***     if no such Cell exists, stop                                   ***/
   /***     otherwise, if h's object value < h's parent's object value     ***/
   /***     then swap h's object with h's parent's object,                 ***/
   /***     set h = h's parent,                                            ***/
   /***     and repeat                                                     ***/
   /***--------------------------------------------------------------------***/
   void heapifyUp()
   {
      Cell h;
      Object obj;

      if (head == null || (head == tail && tail.leftChildOf() == null)) return;
      if (tail.rightChildOf() == null && tail.leftChildOf() == null)
         h = tail.leftNextOf().rightChildOf();
      else
         h = tail.leftChildOf();

      while (true)
      {
         if (h == head) break;
         if (valuefunc(h.objectOf()) < valuefunc(h.parentOf().objectOf()))
         {
            obj = h.objectOf();
            h.setObject(h.parentOf().objectOf());
            h.parentOf().setObject(obj);
            h = h.parentOf();
         }
         else
            break;
      }
   }

   void putRoot(Object obj)
   {
      if (obj == null) return;
      if (head == null) return;
      head.setObject(obj);
   }

   /***--------------------------------------------------------------------***/
   /***  Add a Cell to the end of a heap and insert an object in that Cell ***/
   /***--------------------------------------------------------------------***/
   void addNode(Object obj)
   {
      if (obj == null) return;
      if (head == null)
          head = tail = new Cell(obj, null, null);
      else
      if (tail.leftChildOf() == null)
      {
         if (tail.leftNextOf() == null)
         {
            tail.setLeftChild(new Cell(obj, tail, tail));
            tail.setRightNext(tail.leftChildOf());
         }
         else
         {
            Cell last = tail.leftNextOf().rightChildOf();
            tail.setLeftChild(new Cell(obj, last, tail));
            last.setRightNext(tail.leftChildOf());
         }
      }
      else
      {
         Cell last = tail.leftChildOf();
         tail.setRightChild(new Cell(obj, last, tail));
         last.setRightNext(tail.rightChildOf());
         tail = tail.rightNextOf();
      }
   }

   void display()
   {
      if (head == null) { System.out.println("(empty)"); return; }
      for (Cell t = head ; t != null ; t = t.rightNextOf())
         System.out.print(t.objectOf() + " ");
      System.out.println();
   }

   boolean empty() { return head == null; }
}

public class HeapSort
{
   /***--------------------------------------------------------------------***/
   /***   Perform the heapsort on a binary tree T that is assumed a heap   ***/
   /***--------------------------------------------------------------------***/
   static void heapSort(BinTree T)
   {
      while (!T.empty())
      {
         ((BigInt)(T.getRoot())).display();
         T.putRoot(T.popNode());
         T.heapifyDown();
      }
   }

   /***--------------------------------------------------------------------***/
   /***                      Test of the above functions                   ***/
   /***--------------------------------------------------------------------***/
   public static void main(String args[])
   {
      BinTree T = new BinTree();

      for (int i=29 ; i > 0 ; i--) T.addNodeToHeap(new BigInt(i));
      T.display();
      System.out.println("******");
      heapSort(T);
      System.out.println();
   }
}