0
Save people, I have the following problem, I am implementing a code that returns me the median of a sequence, using max-heap and min-heap. Even before completing the code the compiler returned me an error:
method compareTo in interface java.lang.Comparable<T> cannot be applied to gives type; required: Key found java.lang.Comparable reason actual argument java.lang.Comparable cannot be converted to Key by method invocation conversion
In the case both max-heap and min-heap return a type Key (left.max() method). Also in the assignment v = left.max();
the compiler is barking, I have hunted the error, but I did not find, if you can help me thank.
package median;
public class MedianPQ <Key extends Comparable<Key>>{
private MaxPq left;
private MinPq right;
public MedianPQ(int N, int M) {
left = new MaxPq(N);
right = new MinPq(M);
}
private boolean less( Key k) {
return k.compareTo(left.max()) < 0;
}
public void insert(Key k) {
Key v;
if( left.isEmpty() && right.isEmpty()) v = k;
else {
if( less(k) && (left.size() <= right.size() + 1)) {
left.insert(k);
v = left.max();
}
}
}
Example of the class max-heap (the class min-heap is essentially the same):
public class MaxPq <Key extends Comparable <Key>>{
private Key[] pq;
private int N = 0;
public MaxPq(int maxN) {
pq = (Key[]) new Comparable[maxN + 1];
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void insert( Key v) {
pq[++N] = v;
swin(N);
}
private boolean less( int i, int j) {
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i, int j) {
Key t = pq[i]; pq[i] = pq[j]; pq[j] = t;
}
public void swin( int k) {
while ( k > 1 && less(k/2, k)) {
exch(k/2, k);
k = k/2;
}
}
public void sink( int k) {
while( 2*k <= N) {
int j = 2*k;
if( j < N && less(j, j+1)) j++;
if( !less( k, j)) break;
exch(k, j);
k = j;
}
}
public Key delMax() {
Key max = pq[1];
exch(1, N--);
pq[N+1] = null;
sink(1);
return max;
}
public Key max () {
return pq[1];
}
}
From what I understand he’s squeaking that
left.max()
returns aComparable
. I don’t know the classes you’re using but I think you could cast(Key)left.max()
or else make a trade, make areturn left.max().compareTo(k) < 0;
but all these are kicks based on syntax without taking into account the semantics, ie without taking into account the meaning of this in the code.– Piovezan
I edited the question including max-heap
– Marcelo de Sousa