--- 数据结构 优先级队列 --- java

之前提高到队列是一种先进先出的结构，但是在某些情况下操作的数据具有优先级，那么对他先进行操作，这时队列就不能满足需求了，因为队列只能操作对头的元素，而具有优先级的数据不一定是在对头，这样就需要优先级队列（PriorityQueue）了，优先级队列能返回优先级高的数据，添加新的对象

PriorityQueue的底层使用了堆这个数据结构

堆的概念

对于一个数据的集合1 2 3 4 5 6 7 8，以完全二叉树的顺序储存方式储存在一起，若根节点的值始终大于孩子节点堆叫做大根堆，根节点小于孩子节点的叫做小根堆

以完全二叉树的储存方式储存的数据，但是实际上储存在数组中，在后面标上的下标可以得出

根节点 i 对应的子节点的下标 左节点 i * 2 +1 右节点 i * 2 + 2  i为根节点的下标

堆的实现

字段设计

userSize记录有效数据的个数，数组array储存数据

createHeap 创建堆 大根堆

向下调整 因为初始时的数组并不是一个堆，那么就需要从最后开始堆他开始调整，根据对应i 的左节点为 i*2 +1右节点是i*2+2，如果根节点小于子节点，那么就和他进行交换，若 i 的父节点J

若J右小于 i 交换后的值，那么还需要进行交换，小于就退出，大于一直交换，直到根节点结束

节点 i 对应父节点  (i-1)/2          左节点 (i*2+1)         右节点 (i*2+2)

每次进行向下调整，交换的是左右节点最大的和根节点交换然后让节点 i 走到交换和他交换的子节点继续进行向下调整

将初始数组变为堆

向下调整

push 插入元素 向上调整

每次插入的位置是在useSize指向的下表位置，然后从这个下标开始进行向上调整 创建的是大根堆

push

向上调整

poll 删除的是堆顶的元素

将堆顶元素和堆尾元素交换，然后useSize--，最后再最堆顶元素进行向下调整

peek 获得堆顶元素

直接返回0下标的数据就好

对于数据优先级，这时放再堆顶的元素优先级就是最高的，每次出出去的就是优先级最高的

再java中内置的优先级队列时PriorityQueue 

add 和offer俩方法都是一样的，add会调用offer这个方法

对的使用

可以使用对来解决 top-k的问题，找到k个最大的或者k个最小的数据

只需要先创建k个大小的优先级队列，找最大的就是建小堆，小的建大堆，这时堆顶就是这个堆中最小的数据，然后将要插入的元素和堆顶元素比较，若大于堆顶就删除堆顶元素，并插入元素

END