Java的PriorityQueue与最小堆有何不同？

| 如果您无法插入WithPriority，它们为什么命名为“ 0”？看起来非常类似于堆。有什么区别吗？如果没有区别，那为什么命名为“ 0”而不是“堆”？

已邀请:

6 个回复

Add（）的工作方式类似于insertWithPriority。您可以使用构造函数为所需的类型定义优先级：

PriorityQueue(int, java.util.Comparator)

在http://download.oracle.com/javase/1,5.0/docs/api/java/util/PriorityQueue.html下查看比较器给出的顺序将代表队列中的优先级。

羔磺

默认的PriorityQueue是用Min-Heap实现的，也就是说，top元素是堆中的最小元素。为了实现最大堆，您可以创建自己的比较器：

import java.util.Comparator;

public class MyComparator implements Comparator<Integer>
{
    public int compare( Integer x, Integer y )
    {
        return y - x;
    }
}

因此，您可以通过以下方式创建最小堆和最大堆：

PriorityQueue minHeap=new PriorityQueue();
PriorityQueue maxHeap=new PriorityQueue(size, new MyComparator());

骨乏唯瓜

对于最大堆，您可以使用：

PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());

吐兄

从PriorityQueueJavaDocs：基于优先级堆的无界优先级队列。优先级队列的元素根据其自然顺序或在队列构造时提供的“ 7”进行排序，具体取决于所使用的构造函数。优先级是队列中对象的固有属性。根据某种比较对元素进行排序。要插入具有给定优先级的对象，只需设置对象上影响排序的任何字段，然后“ѭ8”。而且，正如@Daniel所说，通常，Java对象是根据它们提供的功能来命名的，而不是根据它们的实现方式来命名的。

粱委教

来自Java文档优先级队列表示为平衡的二进制堆：queue [n]的两个子级是queue [2 * n + 1]和queue [2 *（n + 1）]。优先级队列由比较器或元素的自然顺序进行排序。这是使用PriorityQueue的maxHeap和minHeap的工作代码-

class HeapDemo {
    private final static int HEAP_SIZE = 10; //size of heap

    //INNER CLASS
    static class maxHeapComparator implements Comparator<Integer> {
        @Override
        public int compare (Integer x, Integer y) {
            return y-x; //reverse order
        }
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(HeapDemo.HEAP_SIZE); 
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(HeapDemo.HEAP_SIZE, new maxHeapComparator());  

        for(int i=1; i<=HeapDemo.HEAP_SIZE; ++i){
            int data = new Random().nextInt(100) +1; //number between 0 to 100
            minHeap.add(data);
            maxHeap.add(data);
        }

        System.out.print(\"\\nMIN Heap : \");
        Iterator<Integer> iter = minHeap.iterator();
        while(iter.hasNext()){
            System.out.print(iter.next() + \" \");
        }

        System.out.print(\"\\nMAX Heap : \");
        iter = maxHeap.iterator();
        while(iter.hasNext()) {
            System.out.print(iter.next() + \" \");
        }
    }
}

样本输出/输出：

MIN Heap : 20 32 37 41 53 91 41 98 47 86 
MAX Heap : 98 91 41 53 86 20 37 41 32 47

亨尖玛次酥

来自http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html 基于优先级堆的无界优先级队列。优先级队列的元素根据其自然顺序或在队列构建时提供的比较器进行排序。对于整数，长整型，浮点型，双精度型，字符型，布尔型（即原始数据类型），自然顺序是升序，这就是为什么Arrays.sort（arr）{其中arr是原始数据类型的数组}对值进行排序的原因按升序排列。您可以使用比较器更改自然顺序比较器可以两种方式使用一种方式是DpGeek展示的方式另一种方法是使用匿名类。例如

Arrays.sort(arr, new Comparator<Integer>() {
     public int compare(Integer x, Integer y) {
         return y - x;
     }
});

如果您有java8，则可以使用lambda表达式 Arrays.sort(arr, (Integer x, Integer y) -> y - x); 这按降序对数组arr进行排序

要回复问题请先登录或注册

Java的PriorityQueue与最小堆有何不同？

6 个回复

发起人

java

priority_queue

问题状态

Java的PriorityQueue与最小堆有何不同？

与内容相关的链接

6 个回复

发起人

java

priority_queue

问题状态