「数据结构」优先级队列

🎇个人主页：Ice_Sugar_7

🎇所属专栏：Java数据结构

🎇欢迎点赞收藏加关注哦！

优先级队列

• 🍉前言
• 🍉构造方法
• 🍉基本方法
• 🍉注意事项

  🍉前言

  优先级队列底层是用堆实现的，关于堆的实现，之前的文章已经详细介绍过了，文章链接：二叉树1：堆的实现

  🍉构造方法

  方法	功能
  PriorityQueue()	创建一个空的优先级队列，默认容量是11
  PriorityQueue(int initialCapacity)	创建一个初始容量为initialCapacity的优先级队列（注意：initialCapacity不能小于1，否则会抛IllegalArgumentException异常）
  PriorityQueue(Collection c)	将一个包含指定类型元素的集合c添加到新建的PriorityQueue中
  PriorityQueue(int initialCapacity, Comparator comparator)	使用比较器来初始化PriorityQueue（可以不传initialCapacity，此时使用默认容量）

  注意：要将自定义类型的对象存放到PriorityQueue时，通常需要传入一个比较器，重写compare方法来定义对象之间的优先级顺序

  在Java中，PriorityQueue默认是小堆，如果要将其转化为大堆，就要用比较器初始化PriorityQueue

  public class MaxHeapExample { public static void main(String[] args) { // 创建一个Comparator，定义从大到小的比较规则
          Comparator maxHeapComparator = new Comparator() { @Override
              public int compare(Integer o1, Integer o2) { return o2 - o1; // 从大到小排序
              }
          };
          // 使用maxHeapComparator创建一个大堆PriorityQueue
          PriorityQueue maxHeap = new PriorityQueue<>(maxHeapComparator);
          // 向大堆中添加元素
          maxHeap.add(3);
          maxHeap.add(1);
          maxHeap.add(5);
          maxHeap.add(2);
          // 此时PriorityQueue中的元素将按照大堆的规则排列
          // 输出：[5, 3, 1, 2]
          System.out.println(maxHeap);
      }
  }
  

  ---

  🍉基本方法

  方法	功能
  boolean offer(E e)	插入元素e，插入成功返回true。如果e对象为空，则抛出NullPointerException异常（即不能插入null）
  E peek()	获取优先级最高的元素（就是堆顶元素），如果优先级队列为空，返回null
  E poll()	移除优先级最高的元素并返回，如果优先级队列为空，返回null
  int size()	获取有效元素的个数
  void clear()	清空
  boolean isEmpty()	检测优先级队列是否为空，若为空，则返回true

  ---

  🍉注意事项

  • PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
  • 不能插入null对象，否则会抛出NullPointerException
  • 没有容量限制，可以插入任意多个元素，因为其内部可以自动扩容
  • 插入和删除元素的时间复杂度为O（logN）
  • PriorityQueue默认情况下是小堆——即每次获取到的元素都是最小的元素