什么是PriorityQueue优先级队列，使用PriorityQueue建立大顶堆和小顶堆_java priorityqueue大顶堆

目录

PriorityQueue优先级基本概念

PriorityQueue实现小顶堆

PriorityQueue实现大顶堆

PriorityQueue优先队列的应用场景

PriorityQueue优先级基本概念

• PriorityQueue是Java中的一个优先级队列，它是基于堆（heap）数据结构实现的。
• 在PriorityQueue中，每个元素都有一个优先级，优先级高的元素先被消费。
• PriorityQueue是按照堆的性质来维护元素的顺序，这使得它具有O(log n)时间复杂度的增加和删除元素的操作。
• 在PriorityQueue中，没有随机访问一个元素的方法，因为它不是一个List。
• 一般来说，PriorityQueue会自动根据元素的自然排序对元素进行排序。如果要创建一个使用不同排序方式的PriorityQueue，可以传入一个Comparator对象来进行自定义排序。

PriorityQueue实现小顶堆

以下是一个使用PriorityQueue实现堆(小顶堆)排序算法的示例代码：

import java.util.PriorityQueue;
 
public class HeapSortExample {
    public static void main(String[] args) {
        int[] nums = { 3, 2, 1, 5, 4 };
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : nums) {
            heap.offer(num);
        }
        int i =0;
        while (!heap.isEmpty()) {
            nums[i++] = heap.poll();
        }
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}

该代码的输出结果为：1 2 3 4 5

即PriorityQueue默认小顶堆，即优先级最小的元素位于队列头部。

PriorityQueue实现大顶堆

根据PriorityQueue的构造器，如果想要创建一个大顶堆，则可以传入一个自定义的比较器（Comparator）来指定元素之间的比较方式。

 代码如下：

import java.util.Comparator;
import java.util.PriorityQueue;
 
public class MaxHeapExample {
  public static void main(String[] args) {
    // 自定义比较器，实现大顶堆
    Comparator<Integer> customComparator = new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        return o2 - o1; //反转自然排序的顺序，使其实现大顶堆
      }
    };
 
    // 使用自定义比较器创建一个大小为10的大顶堆 
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(10, customComparator);
    maxHeap.add(3);
    maxHeap.add(1);
    maxHeap.add(6);
    maxHeap.add(9);
 
    //打印优先级队列的元素
    while (!maxHeap.isEmpty()) {
      Integer val = maxHeap.poll();
      System.out.print(val + " ");
    }
  }
}

输出结果为：9 6 3 1可以看到，元素按照从大到小的顺序被输出，表明PriorityQueue创建的是一个大顶堆。

方式二：也可以简化比较器，直接变成如下代码,第二个参数减第一个是大顶堆

import java.util.PriorityQueue;
 
public class MaxHeapExample {
  public static void main(String[] args) {
 
    // 第二个参数减第一个是大顶堆 
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((T1,T2)->T2-T1);
    maxHeap.add(3);
    maxHeap.add(1);
    maxHeap.add(6);
    maxHeap.add(9);
 
    //打印优先级队列的元素
    while (!maxHeap.isEmpty()) {
      Integer val = maxHeap.poll();
      System.out.print(val + " ");
    }
  }
}

方式二的结果也是：9 6 3 1

PriorityQueue优先队列的应用场景

• 从大量任务中，快速找到并处理高优先级任务时，可以使用PriorityQueue实现任务队列。例如，一个多线程爬虫程序需要处理大量URL，可以使用PriorityQueue将URL按照优先级排序，然后多线程并发抓取，优先处理URL的优先级高的页面。
• PriorityQueue也可以应用于实现派发紧急事件的队列，如医疗急救中心的求助电话队列。来自不同人的紧急事件请求被加入到一个优先级队列中，优先级越高代表情况越紧急，紧急事件被按照优先级顺序处理。
• PriorityQueue还可以用于任务调度系统，可以进行实时调度，按任务优先级进行处理。在自动化制造领域，生产线中需要联动多个机器完成生产，可以使用PriorityQueue根据物料到厂时间的差异来调整每个任务的生产时间，确保生产线的顺畅。

以上就是有关PriorityQueue优先队列的知识，特别是关于小顶堆大顶堆的使用！