CODEWITHSUNDEEP
java
Megan
Megan

Reputation: 15

Dealing with repeated elements in Priority Queue in Java

I'm using a Priority Queue to model a min-heap in order to implement Huffman's coding. The problem I found is that whenever a repeated element enters the heap, it goes on top of these repeated elements, just before the next smaller element. What I need is to be able to put this repeated elements at the end of the repeated, as soon as it finds an element that is equal (after the last bigger element).

Example: If I have

[1,2,2,3,4,5,6,7]

and I want to enter another 2, let's mark it 2*, this is what I get:

[1,2*,2,2,3,4,5,6,7]

and this is what I need:

[1,2,2,2*,3,4,5,6,7]

Is there any way I can change the Comparator to achieve this? Or any other solution?

Upvotes: 1

Views: 1432

Answers (2)

Girija Sankar Panda
Girija Sankar Panda

Reputation: 318

Though there is no default implementation of Comparator or Comparable with PriorityQueue but you can customize based on your requirements.

1.create your own Comparator

class NumberComparator implements Comparator<Pair<Integer, ZonedDateTime>> {

public int compare(Pair<Integer, ZonedDateTime> s1, Pair<Integer, ZonedDateTime> s2) {
    if (s1.getKey() < s2.getKey())
        return 1;
    else if (s1.getKey() > s2.getKey())
        return -1;
    else if (s1.getKey() == s2.getKey()) {
        return s1.getValue().isAfter(s2.getValue()) ? -1 : 1;
    }
    return 0;
}}

2.Pass it while creating PriorityQueue

class Example {
public static void main(String[] args) {
   
    
    PriorityQueue<Pair<Integer,ZonedDateTime>> pq = new
            PriorityQueue<>(5, new NumberComparator());
    pq.offer(new Pair(1,ZonedDateTime.now()));
    pq.offer(new Pair(1,ZonedDateTime.now()));
    pq.offer(new Pair(2,ZonedDateTime.now()));
    pq.offer(new Pair(2,ZonedDateTime.now()));
    pq.offer(new Pair(1,ZonedDateTime.now()));


    while (!pq.isEmpty()) {
        Pair<Integer, ZonedDateTime> pair = pq.poll();
        System.out.println(pair.getKey()+"-"+pair.getValue().getNano());
    }
}

}

Upvotes: 1

Naetmul
Naetmul

Reputation: 15592

From Javadoc of PriorityQueue,

If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily.

Therefore, Java's PriorityQueue arbitrarily sorts the same values. It is not customizable unless you extend PriorityQueue or AbstractQueue to make your own priority queue.

You can use a simple pair class to contain both your value and the insertion counter, where the insertion counter may be a member of the queue or a static variable which increases whenever an insertion occurs, and provide a Comparator or implement Comparable that compares the values first, and the insertion counters second if the values are equal.

Upvotes: 1

Related Questions