数据结构—优先级队列（堆）

一.优先级队列的存储

优先级队列存储在一堆数组中，分为大堆和小堆，把二叉树按层序遍历得出的结果存储到优先级队列

二.堆的分类

堆是一颗完全二叉树，堆分为大根堆和小根堆，大根堆根结点比左右孩子结点都大，小根堆相反

三.性质

设i是数组下标

1.i = 0，是根结点

2.结点的双亲结点是（i - 1 ）/ 2

3.（2 * i + 1）是左孩子结点，（2 * i + 2）是右孩子结点

四.代码实现

1.创建

此时默认建立的是小根堆，那么我们如何建立大根堆呢

我们需要重写比较器

但是这种方法不方便更改，那么我们可以用下面的方法

我们可以构建一个比较器生成大根堆

它的好处是如果需要生成小根堆，我们可以重新构建一个比较器将里面的参数换成这个比较器就可以了

2.功能

五.关于PriorityQueue使用时的注意事项：

1.PriorityQueue中放置的元素必须要能够⽐较⼤⼩，不能插⼊⽆法⽐较⼤⼩的对象，否则会抛出 ClassCastException异常

2. 不能插⼊null对象，否则会抛出NullPointerException

3. 没有容量限制，可以插⼊任意多个元素，其内部可以⾃动扩容

4. 插⼊和删除元素的时间复杂度为

5. PriorityQueue底层使⽤了堆数据结构

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

7.当调用grow（扩容）时，如果>64,1.5倍扩容，<64，2倍扩容