I am trying to implement a min heap in java which sorts based on two parameters. Each element of the min heap is an object which contains an int and a string. My current implementation sorts solely based on the integer but I also need it to sort in alphabetical order. For example, if the contents of the objects are as follows:
{ (stopped, 3), (anywhere, 1), (food, 17), (get, 3), (done, 1)}
the output when removing elements from the heap must be:
{(anywhere, 1), (done, 1), (get, 3), (stopped, 3), (food, 17)}
My sink and swim functions are described below:
private void swim(int n){
while (n > 1 && greater(n/2, n)){
exchange(n, n/2);
n = n/2;
}
}
private boolean greater(int i, int j){
return elements[i].getValue() >= elements[j].getValue();
}
private void exchange(int i, int j){
Node tmp = elements[i];
elements[i] = elements[j];
elements[j] = tmp;
}
private void sink(int k){
while(2*k <=n){
int i = 2*k;
if(i < n && greater(i, i+1)) i++;
if(!greater(k,i)) break;
exchange(k,i);
k = i;
}
}
Any help would be greatly appreciated!
Thank you very much to @AlbertoSinigaglia, your solution worked!
you just need to update the greater
method in this way:
return /*1*/ elements[i].getValue()>elements[j].getValue
||
/*2*/ (elements[i].getValue()==elements[j].getValue() && elements[i].getString().compareTo(elements[j].getString())>0)
With 1 you check if the int Value is greater, if yes, well ends there, if else it's not, it should be o =
or <
and we need to take care of the =
case, so if the Values are equals, then we compare the String with the compareTo()
method, which will return >0
in case the first String is greater than the second string