PriorityQueue 的输出因排序和未排序数组而异

Question

我正在实施 Priority Queue，但我无法理解为什么 sorted 和 unsorted 数组有不同的 outputs。代码和输出如下所示：

排序数组

import java.io.*;
import java.util.*;
class Test {
    public static void main(String args[] ) throws Exception {
       PriorityQueue<Integer> pq=new PriorityQueue<>();
       int[] a={0,1,2,3,4,5,6,7,8};
       for (int x:a ) {
        pq.add(x);
       }
       Iterator itr=pq.iterator();
       while(itr.hasNext()){
        System.out.print(itr.next()+" ");
       }
       System.out.println();
    }
}

Output : 0 1 2 3 4 5 6 7 8

未排序数组

import java.io.*;
import java.util.*;
class Test {
    public static void main(String args[] ) throws Exception {
       PriorityQueue<Integer> pq=new PriorityQueue<>();
       int[] a={4,3,6,2,1,5};
       for (int x:a ) {
        pq.add(x);
       }
       Iterator itr=pq.iterator();
       while(itr.hasNext()){
        System.out.print(itr.next()+" ");
       }
       System.out.println();
    }
}

Output : 1 2 5 4 3 6

谁能解释一下为什么这两种情况的输出之间存在差异？

Answer 1

PriorityQueue in Java is implemented as a binary heap。二叉堆中项目的顺序取决于它们被插入的顺序。例如，按顺序插入项目 [1, 2, 3, 4] 会得到堆：

      1
    2   3
  4

但是如果你按 [1, 3, 4, 2] 的顺序插入，那么你的堆将是：

      1
    3   2
  4

请记住，二叉堆不是排序数据结构。它的排序方式是最小的项目（在最小堆的情况下）始终位于根节点，并且子节点大于其父节点。但是对于给定的一组项目，有许多可能的堆排序。

更新

你问了，"how would {4,3,6,2,1,5} be ordered in the heap?"我们来看看吧。

插入 4：{4}
插入 3：{3,4}
插入 6：{3,4,6}
Insert 2：将2加到堆尾：{3,4,6,2}，然后向上筛选。首先它与它的父交换生成 {3,2,6,4}，然后再次与根交换生成 {2,3,6,4}。
插入1：添加到堆的末尾{2,3,6,4,1}。与父 {2,1,6,4,3} 交换，然后与根交换以创建 {1,2,6,4,3}。
插入5：添加到堆尾{1,2,6,4,3,5}。与父交换以创建 {1,2,5,4,3,6}。

PriorityQueue 的输出因排序和未排序数组而异

The output of PriorityQueue varies for sorted and unsorted array

arrays

priority-queue

更新