Best practice in preserving insertion order with priority queue in case of equality for stable sorting

Question

UPDATE

Given a set of reviews provided by the customers for different hotels and a string containing “Good Words”, you need to sort the reviews in descending order according to their “Goodness Value” (Higher goodness value first). We define the “Goodness Value” of a string as the number of “Good Words” in that string.

Note: Sorting should be stable. If review i and review j have the same “Goodness Value” then their original order would be preserved.

Issue Using priority queue to arrange above order is not being stable as while polling heap arrays are not returning in same order for same values.

Meanwhile, I have checked this blog: https://lemire.me/blog/2017/03/13/stable-priority-queues/.

Is there any better way for stable priority queue ordering? or any other better DS? One way I can think of is putting it in arrays and sorting it. Treemap can't be much useful as key with duplicates entries or similar count multiple words are involved.

Question: https://www.interviewbit.com/problems/hotel-reviews/

This works

Input: S = "cool_ice_wifi" R = ["water_is_cool", "cold_ice_drink", "cool_wifi_speed"]

Output: ans = [2, 0, 1]

Here, sorted reviews are ["cool_wifi_speed", "water_is_cool", "cold_ice_drink"]

This test case doesn't work.

A : "a_b_c "
B : [ "a_b", "b_c", "a_c" ]

public class Solution {

  private static final int ALPHA_SIZE = 26;

  public static class Reviews implements Comparable<Reviews> {
    private int pos;
    private int score;

    @Override
    public boolean equals(Object o) {
        if(this == o) return true;
        if(o == null || this.getClass()!=o.getClass()) return false;

        Reviews r = (Reviews)o;
        if(r.score!=this.score) return false;

        return true;
    }

    @Override
    public int compareTo(Reviews r) {
        return this.score - r.score;
    }
  }

  public static class TrieNode {
    TrieNode[] letter;
    boolean isTail;

    public TrieNode() {
        isTail = false;
        letter = new TrieNode[ALPHA_SIZE];
        for(int i = 0; i < ALPHA_SIZE; i++) {
            letter[i] = null;
        }
    }

  }

  static TrieNode root; 

  public static void add(String word) {
    TrieNode curr = root;
    for(char ch : word.toCharArray()) {
        if(curr.letter[ch-'a']==null) curr.letter[ch-'a'] = new TrieNode();
        curr = curr.letter[ch-'a'];
    }
    curr.isTail = true;
  }

  public void addAll(String[] words) {
    for(String word : words) {
        this.add(word);
    }   
  }

  public static boolean contains(String word) {
    TrieNode curr = root;
    for(char ch : word.toCharArray()) {
        if(curr.letter[ch-'a']!=null) {
            curr = curr.letter[ch-'a'];
        } else {
            return false;
        }
    }
    return curr.isTail;
  }

  public ArrayList<Integer> solve(String A, ArrayList<String> B) {

    root = new TrieNode();
    String[] words = A.split("_");
    addAll(words);
    ArrayList<Integer> res = new ArrayList<>();

    Reviews cur;
    Queue<Reviews> q = new PriorityQueue<>(Collections.reverseOrder());
    for(int i = 0; i < B.size(); i++) {
        cur = new Reviews();
        cur.score = countGW(B.get(i));
        cur.pos = i;
        q.add(cur);
    }

    while(!q.isEmpty()) {
        cur = q.poll();
        res.add(cur.pos);
    }

    return res;
  }

  public int countGW(String x) {
    String[] xs = x.split("_");
    int res = 0;

    for(String y : xs) {
        if(contains(y)) {
            res++;
        }
    }

    return res;
  }

}

Answer 1

As others have pointed out, you can't depend on PriorityQueue for a stable sort. The reason is that PriorityQueue is implemented with a binary heap, and binary heap does not produce a stable ordering.

But you can use PriorityQueue in your case. You want to sort by score, with equal scores being returned in order by their pos values. So if you have:

pos   score
 1      1
 2      3
 3      2
 4      1

Then you want the result to be:

pos   score
 2      3
 3      2
 1      1
 4      1

All you have to do is modify your compareTo method so that if score is equal, it compares pos, like this:

@Override
public int compareTo(Reviews r) {
    int result = this.score.compareTo(r.score);
    if (result != 0) return result;
    result = this.pos.compareTo(r.pos);
}

In general, it's a bad idea to use this.score - r.score to do a comparison. It works for positive numbers, but if you mix positive and negative numbers, integer overflow can produce errors. See my blog post, Subtraction is not the same as comparison for the details.