前言

      大家好，我目前在学习java。之前也学了一段时间，但是没有发布博客。时间过的真的很快。我会利用好这个暑假，来复习之前学过的内容，并整理好之前写过的博客进行发布。如果博客中有错误或者没有读懂的地方。热烈欢迎大家在评论区进行讨论！！！

      喜欢我文章的兄弟姐妹们可以点赞，收藏和评论我的文章。喜欢我的兄弟姐妹们以及也想复习一遍java知识的兄弟姐妹们可以关注我呦，我会持续更新滴，

     望支持！！！！！！一起加油呀！！！！

语言只是工具，不能决定你好不好找工作，决定你好不好找工作的是你的能力！！！！！

学历本科及以上就够用了！！！！！！！！！！！！！！！！！！！！！！

本篇博客主要讲解Java基础语法中的

优先级队列、PriorityQueue的特性、常用方法介绍、编程题练习

在上文中，我们已经讲到了优先级队列的概念。本篇文章，我们将更加深入的讲解优先级队列。

《Java初阶数据结构》----6.＜优先级队列之PriorityQueue底层：堆＞

一、 PriorityQueue优先级队列

1.1 PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。

关于PriorityQueue的使用要注意：

1. 使用时必须导入PriorityQueue所在的包，即：  

<code>import java.util.PriorityQueue;

2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常

3. 不能插入null对象，否则会抛出NullPointerException

4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容

5. 插入和删除元素的时间复杂度为

6. PriorityQueue底层使用了堆数据结构

7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素

1.2PriorityQueue常用方法介绍

. 优先级队列的构造：

1.PriorityQueue中常见的几种构造方式

代码示例： 

<code>static void TestPriorityQueue(){

       // 创建一个空的优先级队列，底层默认容量是11

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

       // 创建一个空的优先级队列，底层的容量为initialCapacity

       PriorityQueue<Integer> q2 = new PriorityQueue<>(100);

       ArrayList<Integer> list = new ArrayList<>();

       list.add(4);

       list.add(3);

       list.add(2);

       list.add(1);

       // 用ArrayList对象来构造一个优先级队列的对象

       // q3中已经包含了三个元素

       PriorityQueue<Integer> q3 = new PriorityQueue<>(list);

       System.out.println(q3.size());

       System.out.println(q3.peek());

  }

 注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器

用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可 

// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可

class IntCmp implements Comparator<Integer>{

   @Override

   public int compare(Integer o1, Integer o2) {

       return o2-o1;

  }

}

public class TestPriorityQueue {

   public static void main(String[] args) {

       PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());

       p.offer(4);

       p.offer(3);

       p.offer(2);

       p.offer(1);

       p.offer(5);

       System.out.println(p.peek());

  }

}

 此时创建出来的就是一个大堆。

2. 插入/删除/获取优先级最高的元素

<code>static void TestPriorityQueue2(){

   int[] arr = {4,1,9,2,8,0,7,3,6,5};

   // 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好

   // 否则在插入时需要不多的扩容

   // 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低

   PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);

   for (int e: arr) {

       q.offer(e);

  }

   System.out.println(q.size());   // 打印优先级队列中有效元素个数

   System.out.println(q.peek());   // 获取优先级最高的元素

   // 从优先级队列中删除两个元素之和，再次获取优先级最高的元素

   q.poll();

   q.poll();

   System.out.println(q.size());   // 打印优先级队列中有效元素个数

   System.out.println(q.peek());   // 获取优先级最高的元素

   q.offer(0);

   System.out.println(q.peek());   // 获取优先级最高的元素

   // 将优先级队列中的有效元素删除掉，检测其是否为空

   q.clear();

   if(q.isEmpty()){

       System.out.println("优先级队列已经为空!!!");

}

else{

System.out.println("优先级队列不为空");

}

}

注意：以下是JDK 1.8中，PriorityQueue的扩容方式： 

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {

   int oldCapacity = queue.length;

   // Double size if small; else grow by 50%

   int newCapacity = oldCapacity + ((oldCapacity < 64) ?

                                    (oldCapacity + 2) :

                                    (oldCapacity >> 1));

   // overflow-conscious code

   if (newCapacity - MAX_ARRAY_SIZE > 0)

       newCapacity = hugeCapacity(minCapacity);

   queue = Arrays.copyOf(queue, newCapacity);

}

private static int hugeCapacity(int minCapacity) {

   if (minCapacity < 0) // overflow

       throw new OutOfMemoryError();

   return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}

优先级队列的扩容说明：

如果容量小于64时，是按照oldCapacity的2倍方式扩容的如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容

 1.3编程题练习

最小k个数

class Solution {

   public int[] smallestK(int[] arr, int k) {

       // 参数检测

       if(null == arr || k <= 0)

           return new int[0];

PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);

       // 将数组中的元素依次放到堆中

       for(int i = 0; i < arr.length; ++i){

           q.offer(arr[i]);

      }

       // 将优先级队列的前k个元素放到数组中

       int[] ret = new int[k];

       for(int i = 0; i < k; ++i){

           ret[i] = q.poll();

      }

       return ret;

  }

}

该解法只是PriorityQueue的简单使用，并不是topK最好的做法，那topk该如何实现？

class Solution {

public int[] smallestK(int[] arr, int k) {

int[] vec = new int[k];

Arrays.sort(arr);

for (int i = 0; i < k; ++i) {

vec[i] = arr[i];

}

return vec;

}

}