CODEWITHSUNDEEP
java
Tandura
Tandura

Reputation: 908

Override Integer compareTo? Or trick it?

I am trying to write a generic heap class.

import java.util.ArrayList;

public class heap<T extends Comparable<T>>
{
    private ArrayList<T> h;
    private int size;

    public heap()
    {
        h = new ArrayList<T>();
        h.add(null);
        size = 0;
    }

    public T getMin()
    {
        return h.get(1);
    }

    public T popMin()
    {
        T tmp = getMin();
        h.set(1, h.get(size));
        size--;
        sift(1);
        return tmp;
    }

    public void insert(T key)
    {
        h.add(key);
        percolate(++size);
    }

    public int getSize()
    {
        return this.size;
    }

    private int getLeftSon(int i)
    {
        return (i<<1<=size)? i<<1 : 0;
    }

    private int getRightSon(int i)
    {
         return ((i<<1)+1<=size)? (i<<1)+1 : 0;
    }

    private int getFather(int i)
    {
        return ((i>>1)!=0)? i>>1 : 0;
    }

    private void swap(int i, int j)
    {
        T tmp = h.get(i);
        h.set(i, h.get(j));
        h.set(j, tmp);
    }

    private void sift(int i) 
    {
        int son;
        do {
            son = 0;
            if (getLeftSon(i) != 0) 
            {
                son = getLeftSon(i);
                if (getRightSon(i) != 0 && h.get(getRightSon(i)).compareTo(h.get(getLeftSon(i))) > 0) 
                    son = getRightSon(i);
                if (h.get(son).compareTo(h.get(i)) <= 0) 
                    son = 0;
            }

            if (son!=0) {
                swap(i, son);
                i = son;
            }
         } while (son!=0);
    }

    private void percolate(int i) 
    {
        T key = h.get(i);

        while ((i > 1) && (key.compareTo(h.get(getFather(i))) > 0)) 
        {
            h.set(i, h.get(getFather(i)));
            i = getFather(i);
        }

        h.set(i, key);
    }
}

All good. It works like a charm. Excepting one thing: if I work with Integers I don't have 'access' to the method compareTo from Integer. meaning that I can not override it's behaviour. I will always have a Max heap this way. Can Integer compareTo by override (I don't think it can)? So what can I do apart from creating another class MyInteger extends Integer{...} and override it there.

Upvotes: 1

Views: 503

Answers (1)

Jiri Tousek
Jiri Tousek

Reputation: 12440

You could make your heap accept a Comparator in constructor and then provide a Comparator that reverses the order.

That's what the Comparator is for actually - defining an ordering that's not a natural one for the given class, being able to define multiple orderings of the same class, or indeed defining an ordering for a class you cannot modify.

The approach of accepting a comparator at construction time can be seen in TreeSet for example.

Example code stub:

public class Heap<T> { /* no need for items to extend Comparable anymore */
    private final Comparator<T> cmp;

    public Heap(Comparator<T> cmp) {
        this.cmp = cmp;
        ...
    }

    ...
}

... and then use cmp.compare(item1, item2) wherever you now use item2.compareTo(item2).

Upvotes: 8

Related Questions