Save personal, I have the following problem, I am implementing code that returns me the median of a sequence, using max-heap and min-heap. Before even 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 case both max-heap and min-heap return a Key type (method left.max ()). Also in the% assignment the compiler is crying, I hunt the error, but I did not find it, if you can help me thank you.
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 max-heap class (the min-heap class 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];
}
}