Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java. Is it possible to use a pair in a priority queue and then return a value using the key as a priority

So I want to use the smallest key as the priority and then return the VALUE of that corresponding key:

import javafx.util.Pair;
import java.util.PriorityQueue;

public class Test
{
    public static void main (String[] args)
    {
        int n = 5;

        PriorityQueue <Pair <Integer,Integer> > l = new PriorityQueue <Pair <Integer,Integer> > (n);

        l.add(new Pair <> (1, 90));
        l.add(new Pair <> (7, 54));
        l.add(new Pair <> (2, 99));
        l.add(new Pair <> (4, 88));
        l.add(new Pair <> (9, 89));

        System.out.println(l.poll().getValue()); 
    }
}

The output Im looking for is 90 because 1 is the smallest key. Its fine even if the value is used as the priority and the key is returned because I can just swap the data if neccessary. I want to display key/value using value/key as a priority (minimum value in this case). I do not know how this can be done in this scenario. This works fine in C++.

like image 440
Artaxerxes Avatar asked May 09 '20 19:05

Artaxerxes


2 Answers

You need to use Comparator which will be used to order this priority queue.

Use Comparator.comparing() and pass Method reference of comparing parameter when create the PriorityQueue

PriorityQueue<Pair<Integer,Integer> > pq=
                new PriorityQueue<Pair<Integer,Integer>>(n, Comparator.comparing(Pair::getKey));

Or

You can use lambda expression

PriorityQueue<Pair<Integer,Integer> > pq=
                    new PriorityQueue<Pair<Integer,Integer>>(n,(a,b) -> a.getKey() - b.getKey());
like image 100
Eklavya Avatar answered Sep 29 '22 08:09

Eklavya


Alternative, use custom Pair class that implements Comparable.

class Pair implements Comparable<Pair> {
    Integer value;
    Integer index;

    public Pair(Integer value, Integer index) {
        this.value = value;
        this.index = index;
    }

    @Override
    public int compareTo(Pair o) {
        return value - o.value;
    }
}

and then usage

// Add elements
queue.add(new Pair(valueKey, index));
// do it for all your elements

final Pair min = queue.poll();
Integer index = min.index;
Integer value = min.value;

// Do with them what you want.

I used PriorityQueue in leetcode challenge. https://leetcode.com/problems/merge-k-sorted-lists/discuss/630580/Using-PriorityQueue-in-Java

And this is full example https://github.com/yan-khonski-it/leetcode/blob/master/src/main/java/com/yk/training/leetcode/merge_sorted_lists/PriorityQueueSolution.java

like image 22
Yan Khonski Avatar answered Sep 29 '22 06:09

Yan Khonski