Java PriorityQueue带有自定义对象无法正确排序

Question

我不完全了解如何使用Java Priorityqueue（Max Heap）作为自定义对象。

我正在研究 leetcode问题我的代码必须重新订购。句子中的单词按单词长度。我的本能是，我可以使用优先级为我完成单词顺序的工作。为此，我认为我可以用自定义对象跟踪单词：

public class word implements Comparable<word>{
    public String theWord;
    public int len, order;
    public word(String w, int order) {
        this.theWord = w;
        this.order = order;
        this.len = w.length();
    }
    @Override
    public int compareTo(word o) {
        return this.len - o.len;                    // sorting behavior controlled here, right???
    }
    public String toString() {
        return this.theWord+"("+this.order+") ";    // for troubleshooting
    }
}

然后：

public String arrangeWords(String sentence) {

    PriorityQueue<word> maxHeap = new PriorityQueue<>(Comparator.naturalOrder());
    String[] words = sentence.split(" ");
    for( int i=0; i<words.length; i++ ) {
        maxHeap.offer( new word(words[i], i) );
    }
}

我要测试的第一个句子是“ leetcode很酷>”。 （来自LC帖子。）

订购我 希望 for is：“ is cool leetcode>”（最短的单词顺序）

但是，当我运行上面的代码并检查调试器中的优先级时，我会看到：

is(1)  leetcode(0)  cool(2)

soooo ...什么呢？我根本不明白这是如何订购的。这不是原始顺序（由括号表示），而不是按字母顺序排列的，甚至不是按字母顺序排列。我不知道PriortityQueue如何决定如何订购Word对象。我以为类Word's compareTo（）方法将迫使我想要的订购。 （我已经看到了其他如此帖子。）但事实并非如此。有人看到我出了什么问题吗？谢谢。

Answer 1

您将它们插入优先队列。但是然后您需要 Poll 排队获得正确的单词顺序的队列。

        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());
        }

另外，请注意订单字段不会仅仅因为将其插入优先队列而被更改。它只是显示了单词在原始句子中出现的顺序。

在循环插入的位置之后，在循环之后写下该循环。然后再次执行。您会看到正确的顺序。

Answer 2

Priorityqueue（Minheap）坚持认为最低元素的长度最低。其余元素将以随机顺序为单位。一旦您对顶部元素进行了轮询，然后重新排序就会发生（在技术上令人震惊），从而使剩余的最小元素成为最高元素。正如已经指出的那样，您需要对所有对象进行轮询，并使它们成为句子的一部分。

另外，解决问题的另一种方法是 - ＆gt;您可以简单地使用字符串数组上的比较器。

class Solution {
   public static String arrangeWords(String text) {

        String str[] = text.split(" ");
        Arrays.sort(str, (a, b) -> a.length() - b.length());
        String res = "";
        for ( int i = 0; i< str.length; i++)
        {
            if ( i ==0 )
            {
                res += str[i].substring(0,1).toUpperCase()  + str[i].substring(1) + " ";
            }
            else{
                     res += str[i].substring(0,1).toLowerCase()  + str[i].substring(1) + " ";
            }
        }
        return res.trim();
    }

}