Search code examples
javasortingpriority-queue

Implementation of min Heap with two parameters for sorting [Java]


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!

Update

Thank you very much to @AlbertoSinigaglia, your solution worked!


Solution

  • 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