Creating an Array Heap in Java

Question

So i am trying to make an array based generic heap that i can use with my tester class. Much of what i have is based of my understandings of trees and some research online as well as from my textbook; both which have very limited info on what i am looking for. However, i did manage to get all the methods in need and when i run it, i get this error:

Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable;
    at q1.Heaps.<init>(Heaps.java:23)
    at q1.createGui.<init>(Gui.java:46)
    at q1.Gui.main(Gui.java:18)  

Im guessing it has to do with how i declare and initialize my Comparable array, which i am having trouble figuring out how to.

package q1;

import java.util.Arrays;


public class Heaps<E extends Comparable<E>> {

    Comparable[] data;
    int size;

    /**
     * Constructor with s as size
     */
    @SuppressWarnings("unchecked")
    public Heaps(int s) {
        size = 0;
        data = (E[]) new Object[s];
    }

    /**
     * Adds a value to the heap
     */
    public void add(E value) {
        if (full()) // expand array
            ensureCapacity(2*size);
        size++;
        data[size] = value;
        if (size > 1)
            heapifyUp();
    }

    /**
     * Checks if the array is full
     */
    private boolean full()
    { 
        return (size == data.length-1);
    }

    private void heapifyUp()
    {
        Comparable<E> temp;
        int next = size;
        while (next != 1 && data[next].compareTo(data[next/2]) > 0)
        {
            temp = data[next];
            data[next] = data[next/2];
            data[next/2] = temp;
            next = next/2;
        }
    }

    private void heapifyDown()
    {
        Comparable<E> temp;
        int next = 0;
        while (next*2 <= size) // node has a child
        {
            int child = 2*next; // left child
            if (child < size &&
                    data[child].compareTo(data[child+1]) > 0)//left smaller than right
                child++; // right child instead
            if (data[next].compareTo(data[child]) > 0)
            {
                temp = data[next];
                data[next] = data[child];
                data[child] = temp;
                next = child;
            }
            else;
            next = size; // stop loop
        }//end while
    }

    /**
     * Removes all occurrence of element
     */
    public boolean removeAll(E element) {
        if (contains(element) && !(isEmpty())){
            for (int i = 0; i < size; i++){
                if(element.equals(data[i])){
                    data[i] = data[size-1];
                }
                heapifyDown();
            }
            return true;
        }
        return false;
    }

    /**
     * Removes 1st occurrence of element
     */
    public boolean remove(E element) {
        if (contains(element) && !(isEmpty())){
            for (int i = 0; i < size; i++){
                if(element.equals(data[i])){
                    data[i] = data[size-1];
                    heapifyDown();
                    return true;
                }   
            }
        }
        return false;
    }

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

    public Comparable<E>[] ensureCapacity(int s) {
        return Arrays.copyOf(data, 2*s);
    }

    /**
     * Converts the heap into its String representation.
     *   @return the String representation
     */

    public Comparable<E>[] iteratorPreOrder() 
    {
        Comparable<E>[] temp = (E[]) new Object[size];
        temp[0] = data[0];
        int i = 1;
        int count = 1;
        while(data[2*i] != null){
            temp[count] = data[2*i];
            ++i;
            ++count;
        }
        i = 1;
        while(data[(2*i) +1] != null){
            temp[count] = data[(2*i) +1];
            ++i;
            ++count;
        }
        return temp;
    }


    public int countOccurance(E element){
        int count = 0;
        for (int i =0; i < size; i++){
            if(element.equals(data[i])){
                count++;
            }
        }
        return count;
    }

    public boolean contains (E element) 
    {
        for (int i=0; i<size; i++){
            if (element.equals(data[i])){
                return true;
            }
        }
        return false;
    }
}

If you could please show me how i would solve this problem, i would greatly appreciate it. Thanks

EDIT: SO i edited the my class and now it works when i do data = (E[]) new Comparable[s]. So why does java not allow generic Array types, what makes it different from Arraylist, Stacks, Queues, and/or LinkedList which can be generic?

Answer 1

You are creating an Object[] and then trying to cast it to a Comprable[]. The compiler was telling you what you did wrong with the unchecked cast error.

You want data to be E[] data and the line to be:

data = new E[s];

Note: this could run into issues with how Java handles generics.