java - 为什么使用 Offer() 在 java 中填充优先级队列会按字母顺序填充它，同时它还优先考虑大写单词？

Question

我很困惑。 Offer() 按字母顺序填充列表，并且它也优先考虑大写单词。如何按照我键入的顺序填充列表？

import java.util.*;
public class Bucky {

 public static void main(String[] args) {
  PriorityQueue<String> q= new PriorityQueue<String>();
  q.offer("first");
  q.offer("aecond");
  q.offer("zhird");

  System.out.printf("%s ",q);
  System.out.println();
  System.out.printf("%s ", q.peek());
  System.out.println();


 }

}

o/p= [aecond, first, zhird] 第二个

---

import java.util.*;
public class Bucky {

 public static void main(String[] args) {
  PriorityQueue<String> q= new PriorityQueue<String>();
  q.offer("first");
  q.offer("aecond");
  q.offer("Zhird");

  System.out.printf("%s ",q);
  System.out.println();
  System.out.printf("%s ", q.peek());
  System.out.println();


 }

}

o/p= [Zhird, first, aecond] 志德

Answer 1

我认为您要质疑的是数组中项目的顺序。也就是说，当您执行 System.out.printf("%s ",q); 行时，您会得到输出 [Zhird, first, aecond]，并且你想知道为什么数组中的第二项是 first，而它在字典序上大于 aecond。

答案在于优先级队列的结构。它的结构为 binary heap , 并且受制于二叉堆的构建方式。

您的代码像这样构建堆:

q.offer("first");
q.offer("aecond");
q.offer("Zhird");

如果我们把堆想象成一棵树，你会更容易看出会发生什么。第一个调用将 "first" 放在树的根部。创建二叉堆的规则规定，在下一次调用时，字符串 "aecond" 将被放置在最低、最左边的位置，然后重新排列树。所以首先你有:

       "first"
      /
  "aecond"

然后，您沿着树往上爬。如果 child 比 parent 小，那么你交换 parent 和 child 。所以在这种情况下，你最终会得到这棵树:

       "aecond"
      /
  "first"

现在，字符串 "Zhird" 出现了。它被添加到最低、最左边未被占用的位置:

       "aecond"
      /       \
  "first"   "Zhird"

又到了重新排列树的时候了。 "Zhird" 在字典序上比 "aecond" 小，所以它们被交换了:

       "Zhird"
      /       \
  "first"   "aecond"

请注意，这仍然是一个有效的堆。子节点大于父节点。

二叉堆的数组表示基本上只是树的广度优先遍历，所以这棵树表示为["Zhird", "first", "aecond"].

如果你要从堆中一个一个地删除项目，你会以正确的顺序获取它们(即“Zhird”、“aecond”、“first”)。但是数组表示可能与严格的字典顺序有很大不同，因为删除过程会重新排列树。事实上，如果您要从队列中删除第一项(即调用 q.poll)，然后输出数组，您会看到它已被重新排序为 ["aecond", "first"].

查看我的博客，http://blog.mischel.com/2013/09/29/a-better-way-to-do-it-the-heap/ , 堆插入和移除规则的解释。请参阅后续文章，http://blog.mischel.com/2013/09/30/a-simple-heap-of-integers/ ，对于应该帮助您理解树如何映射到数组的实现。

此外，如果您要按此顺序填充堆:

q.offer("Zhird");
q.offer("first");
q.offer("aecond");

输出将是[Zhird, first, aecond]。但如果您的订单是:

q.offer("Zhird");
q.offer("aecond");
q.offer("first");

输出将是[Zhird, aecond, first]。