1

我知道最小堆是该类由于其效率而使用的结构。在我看来，当将未排序的数据提供给 PQ 时，它会将其排序到堆中。

但是，当根据 compareTo 方法向其馈送升序元素时，它会在 PQ 上执行第一个操作后等待将其排序到堆中。

你知道这是为什么吗？我不明白为什么它不像无序数据那样自动排序。

我附上了一个我认为可以证明我的问题的程序。

输出：

未排序的数据：

[A、B、D、C、L、F、E、J]

一个

[B、C、D、J、L、F、E]

[1、2、4、3、12、6、5、10]

1

[2、3、4、10、12、6、5]

排序数据：

[A、B、C、D、E、F、G、H]

一个

[B、D、C、H、E、F、G]

[1、2、3、4、5、6、7、8]

1

[2、4、3、8、5、6、7]

import java.util.PriorityQueue;

public class Queue2
{
    public static void main(String[] args)
    {
        PriorityQueue<String> pQueue = new PriorityQueue<String>();

        pQueue.add("A");
        pQueue.add("C");
        pQueue.add("F");
        pQueue.add("B");
        pQueue.add("L");
        pQueue.add("D");
        pQueue.add("E");
        pQueue.add("J");
        System.out.println(pQueue); 
        System.out.println(pQueue.remove());
        System.out.println(pQueue);

        System.out.println();

        PriorityQueue<Integer> pQueue2 = new PriorityQueue<Integer>();

        pQueue2.add(1);
        pQueue2.add(3);
        pQueue2.add(6);
        pQueue2.add(2);
        pQueue2.add(12);
        pQueue2.add(4);
        pQueue2.add(5);
        pQueue2.add(10);
        System.out.println(pQueue2); 
        System.out.println(pQueue2.remove());
        System.out.println(pQueue2);

        System.out.println();

        PriorityQueue<String> pQueue3 = new PriorityQueue<String>();

        pQueue3.add("A");
        pQueue3.add("B");
        pQueue3.add("C");
        pQueue3.add("D");
        pQueue3.add("E");
        pQueue3.add("F");
        pQueue3.add("G");
        pQueue3.add("H");
        System.out.println(pQueue3); 
        System.out.println(pQueue3.remove());
        System.out.println(pQueue3);

        System.out.println();

        PriorityQueue<Integer> pQueue4 = new PriorityQueue<Integer>();

        pQueue4.add(1);
        pQueue4.add(2);
        pQueue4.add(3);
        pQueue4.add(4);
        pQueue4.add(5);
        pQueue4.add(6);
        pQueue4.add(7);
        pQueue4.add(8);
        System.out.println(pQueue4); 
        System.out.println(pQueue4.remove());
        System.out.println(pQueue4);

    }
}
4

2 回答 2

2

来自PriorityQueue的文档

此队列的头部是相对于指定排序的最小元素。如果多个元素以最低值绑定，则头部是这些元素之一——绑定被任意打破。队列检索操作 poll、remove、peek 和 element 访问队列头部的元素。

和

此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选方法。方法 iterator() 中提供的 Iterator 不能保证以任何特定顺序遍历优先级队列的元素。如果您需要有序遍历，请考虑使用 Arrays.sort(pq.toArray())。

这就是为什么当您在内部打印队列（使用 System.out）时使用迭代器，因此不保证已排序的输出......但是如果您poll()多次使用，您肯定会看到在这两种情况下都以有序方式返回的对象

于 2013-05-28T14:58:28.727 回答
0

所以你知道队列下面有一个（二进制）堆，对吧？堆应该遵守两个属性：

  • shape属性：树是完全二叉树；也就是说，除了最后一层（最深）之外，树的所有层都被完全填满，如果树的最后一层不完整，则该层的节点从左到右被填满。
  • 堆属性：根据为数据结构定义的比较谓词，每个节点都大于或等于其每个子节点。

那么元素是如何插入的呢？只需执行 BFS，直到找到一个空点（将元素放在该点），或者找到另一个比当前元素大的元素（用新元素替换那个元素并继续使用更大的元素）。

让我们来看看你的两个例子。我将逐级编写树，因此[A][BC][D---]表示以树A为根、B的C子级A和D的子级的树B。

让我们看第一个例子：[A, C, F, B, L, D, E, J]. 这就是堆的增长方式：

[A]
[A][C-]
[A][CF]
[A][BF][C---]
[A][BF][CL--]
[A][BD][CLF-]
[A][BD][CLFE]
[A][BD][CLFE][J-------]

现在看看你排序的例子：[A, B, C, D, E, F, G, H]。这就是堆的增长方式：

[A]
[A][B-]
[A][BC]
[A][BC][D---]
[A][BC][DE--]
[A][BC][DEF-]
[A][BC][DEFG]
[A][BC][DEFG][H-------]

事实上，底层数组包含排序顺序的所有元素。

那么，为什么当第一个元素被移除时这个顺序会被扭曲呢？为了满足这两个堆属性，空点重复地用该点的最小子节点填充。

让我们看一下删除后的最后一个示例A（我用 标记了空白处*）：

[*][BC][DEFG][H-------]
[B][*C][DEFG][H-------]
[B][DC][*EFG][H-------]
[B][DC][HEFG]

这也对应于您给出的输出。

于 2013-05-28T14:54:24.337 回答