Heap for a general Object

Question

I am writing a Heap (Max-Heap, meaning max element is root) class that can be used to "heapify" a given set of objects. I am aware of the general structure of this heap and also the various algorithms. Now for a general Object, comparison is not defined. So I need to define the comparison between two objects. My question is if this comparison function should be defined in the class heap or in the class Object? If I define it in class Heap then for every data structure that I use I need to rewrite the comparison function which is not efficient. This is because if I change the Object slightly I might end up changing the comparison at huge number of places. So how is this thing handled? Thank you.

 class Object{
     int value;
     Object (int a) {
         value=a;
     }

     boolean isLessThan(Object a, Object b){
         if (a.value<=b.value){
             return true;
         }
         else return false;
     }
 }

 class Heap{
     Object [] heap=new Object[1000];
     int size=0;
     Heap() {        
     }

     void HeapifyDownwards (int index){
         int left_child=2*index+1;
         int right_child=2*index+2;

         if (size>right_child){
             // both right and left child exist
             Object right= heap[right_child];
             Object left= heap[left_child];
             Object node = heap[index];

             if ((isLessThanEqualTo(right,node)) && (isLessThanEqualTo(left,node))){
                 return;
             }
         }
         else if (size==right_child){
             //only left child exists
         } 
         else {
             // no child exists
         }
     }
 }

Answer 1

Ok! The solution is to use Comparable instead of Objects. Then use node.compareTo(right) (etc.) for the comparisons!

See this link for some more details: Abstract Object Comparison in Java

public class Heap{
    Comparable [] heap=new Comparable[1000];
    int size=0;
    Heap() {        
    }
    public void HeapifyDownwards (int index){
        int left_child=2*index+1;
        int right_child=2*index+2;

        Comparable right= heap[right_child];
        Comparable left= heap[left_child];
        Comparable node = heap[index];

        if (size>right_child){
            // both right and left child exist
            if ((node.compareTo(right)>0) && (node.compareTo(left)>0)){
                return;
            }
            else if ((right.compareTo(node)>0) && (right.compareTo(left)>0)){
                Comparable temp=right;
                heap[right_child]=node;
                heap[index]=temp;
                HeapifyDownwards(right_child);
            }
            else if ((left.compareTo(node)>0) && (left.compareTo(right)>0)){
                Comparable temp=left;
                heap[left_child]=node;
                heap[index]=temp;
                HeapifyDownwards(left_child);
            }
        }
        else if (size==right_child){
            //only left child exists
            if (left.compareTo(node)>0){
                Comparable temp=left;
                heap[left_child]=node;
                heap[index]=temp;
                HeapifyDownwards(left_child);
            }
            else {return;}
        } 
        else {
            return;
        }
    }
    public void HeapifyUpwards (int index){
        int parent_index=(index-1)/2;

        Comparable parent= heap[parent_index];
        Comparable node = heap[index];

        if (node.compareTo(parent)>0){
            Comparable temp= parent;
            heap[parent_index]=node;
            heap[index]=temp;
            HeapifyUpwards(parent_index);
        }
        else{
            return;
        }
    }
    public void Insert (Comparable in){
        heap[size]=in;
        size++;
        HeapifyUpwards(size-1);
    }
    public Comparable Remove (){
        Comparable out=heap[0];
        heap[0]=heap[size-1];
        size--;
        HeapifyDownwards(0);
        return out;
    }
}


public class TestObject implements Comparable{
    int value;
    TestObject (int a) {
        value=a;
    }

    @Override
    public int compareTo (Object b){
         if (this.getClass() == b.getClass()){
            TestObject b_test = (TestObject) b;
            if (this.value<b_test.value){
                return -1;
            }
            else if(this.value==b_test.value){
                return 0;
            }
            else return 1;
         }
         else return -1;
    }

    public void Print (){
        System.out.println(value);
    }
}

Answer 2

The general way such things are handled in Java is either to:

1. Restrict the elements stored in the data structure to implement Comparable, or
2. Store a comparator in the heap object (set at construction time).

Take a look at the TreeSet class in the Java API for an example.

Note that because Java is a (mostly) statically-typed language, the use of generics for such a data structure is very common. They are probably worth learning, although I can understand the desire to just get the heap class working for a particular kind of object.

Also, if the purpose of this exercise is to learn how heaps work, then great. If you actually want a priority queue for a Java application, Java already has a PriorityQueue class.