在稳定排序相等的情况下使用优先队列保留插入顺序的最佳实践

Question

更新

给定一组客户对不同酒店的评论和一个包含“Good Words”的字符串，您需要根据“Goodness Value”（较高的goodness value 在前）对评论进行降序排序。我们将一个字符串的“Goodness Value”定义为该字符串中“Good Words”的数量。

注意：排序应该是稳定的。如果评论 i 和评论 j 具有相同的“Goodness Value”，那么它们的原始顺序将被保留。

问题使用 priority queue 排列上述顺序并不稳定，因为轮询堆数组不会以相同的顺序返回相同的值。

同时，我查看了这个博客：https://lemire.me/blog/2017/03/13/stable-priority-queues/。

有没有更好的方法来稳定优先级队列排序？或者其他更好的DS？我能想到的一种方法是将它放在 arrays 和 sorting 中。 Treemap 没有太大用处，因为 key 涉及重复条目或类似的多个单词。

问题: https://www.interviewbit.com/problems/hotel-reviews/

这个有效

输入： S = "cool_ice_wifi" R = ["water_is_cool"、"cold_ice_drink"、"cool_wifi_speed"]

输出： ans = [2, 0, 1]

这里，排序的评论是["cool_wifi_speed"、"water_is_cool"、"cold_ice_drink"]

这个测试用例不工作。

一个："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

Why PriorityQueue is not working as a stable sorting this case?

因为PriorityQueue没有提供稳定的排序。请参阅 Javadoc。

编辑现在你已经完全改变了你的问题：

Best practice ...

只有一种做法。将插入顺序字段添加到您的对象并将其用作次键。

Answer 2

正如其他人所指出的，您不能依赖 PriorityQueue 进行稳定排序。原因是PriorityQueue是用二叉堆实现的，而二叉堆并没有产生稳定的排序。

但是您可以在您的情况下使用PriorityQueue。您想要按 score 排序，并按 pos 值的顺序返回相同的分数。所以如果你有：

pos   score
 1      1
 2      3
 3      2
 4      1

那么你想要的结果是：

pos   score
 2      3
 3      2
 1      1
 4      1

你所要做的就是修改你的 compareTo 方法，这样如果 score 相等，它就比较 pos，像这样：

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

一般来说，用this.score - r.score做比较是个坏主意。它适用于正数，但如果混合使用正数和负数，整数溢出会产生错误。有关详细信息，请参阅我的博客 post、Subtraction is not the same as comparison。

在稳定排序相等的情况下使用优先队列保留插入顺序的最佳实践

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

java

sorting

priority-queue

trie

data-structures