自定义对象排序不正确的Java PriorityQueue[重复]

Question

我不完全理解如何对自定义对象使用Java PriorityQueue（最大堆）。

我正在研究LeetCode问题，代码必须按单词长度对句子中的单词重新排序。我的直觉是，我可以使用PriorityQueue来为我进行单词排序。为此，我想我可以使用自定义对象跟踪单词：

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帖子。）

我希望的顺序是：“是很酷的leetcode”（最短到最长的语序）

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

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

所以。。。搞什么鬼？我根本不明白这是怎么订购的。这不是原始顺序（用括号表示），不是按长度顺序，甚至不是按字母顺序。我不知道PriorityQueue是如何决定如何对word对象排序的。我认为class word的compareTo（）方法将强制执行我想要的排序。（我在其他SO帖子中看到过这一点。）但事实并非如此。有人知道我做错了什么吗？非常感谢。

Answer 1

PriorityQueue（minHeap）坚持顶部元素的长度最低。其余元素将按随机顺序排列。一旦您轮询顶部元素，然后会发生重新排序（upHeapify-技术上），使剩余元素中最小的成为顶部元素。正如已经指出的，您需要轮询所有对象并使它们成为您句子的一部分。

另外，解决这个问题的另一种方法是-

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();
    }

}

Answer 2

您将它们插入了优先级队列。但是，您需要轮询队列，以获得正确的单词顺序。

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

此外，请注意，不会仅仅因为您在优先级队列中插入了顺序字段而对其进行更改。它只显示单词在原句中出现的顺序。

在插入的循环之后编写该循环。然后再次执行。您将看到正确的顺序。