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

我很困惑。 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 =
[第二，第一，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，第一，第二]
希尔德

最佳答案

我认为您要质疑的是数组中项目的顺序。也就是说，当您执行行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"

然后，您沿着树往上走。如果子项小于父项，则交换父项和子项。因此，在这种情况下，您最终得到树：

       "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]。