Reputation: 15
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
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
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