1 优先级队列
1.1概念
元素不再按照“先进先出”（FIFO）的顺序出队，而是按照“优先级”的高低出队。优先级最高的元素最先出队。
2 优先级队列的模拟实现
优先级队列底层使用了堆这种数据结构，而堆就是在完全二叉树的基础上进行了调整
2.1有关堆的概念
是一个完全二叉树，并且树中任意一个节点的值都必须大于等于（或小于等于）其子节点的值。
满足这个条件是堆
大根堆：任何一个父节点的值，都大于或等于其左右子节点的值。
小根堆：任何一个父节点的值，都小于或等于其左右子节点的值。
2.2堆的存储方式
堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储，
2.3堆的创建
对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据如何将其创建成堆呢？
public class TestHeap {
private int[] elem;
private int usedSize;
public TestHeap(){
this.elem = new int[10];
}
public void initHeap(int[] array){
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
}
public void creatHeap(){
for(int parent = (usedSize-2)/2; parent >=0; parent-- ){
shiftDown(parent,usedSize);
}
}
private void shiftDown(int parent,int usedSize){
int child = 2*parent +1;
while(child < usedSize){
if(child+1 < usedSize && elem[child] < elem[child+1]){
child++;
}
if(elem[parent] < elem[child]){
swap(child,parent);
parent = child;
child = 2*child+1;
}else{
break;
}
}
}
private void swap(int i,int j){
int temp = elem[i];
elem[i] = elem[j];
elem[j] = temp;
}
}
2.4 建堆的时间复杂度
建堆的时间复杂度为O(N)。
2.5 堆的插入与删除
2.5.1堆的插入
堆的插入总共需要两个步骤： 1. 先将元素放入到底层空间中(注意：空间不够时需要扩容) 2. 将最后新插入的节点向上调整，直到满足堆的性质
public void offer(int val){
if(usedSize == elem.length){
this.elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize] = val;
usedSize++;
shiftUp(usedSize);
}
private void shiftUp(int child) {
int parent = (child-1)*2;
while(child > 0) {
if (elem[parent] < elem[child]) {
swap(parent, child);
child = parent;
parent = (parent-1)/2;
}else{
break;
}
}
}2.5.2堆的删除
堆删除的一定是堆顶元素，具体如下： 1. 将堆顶元素对堆中最后一个元素交换 2. 将堆中有效数据个数减少一个 3. 对堆顶元素进行向下调整
3.常用接口介绍
3.1 PriorityQueue特性
1. 使用时必须导入PriorityQueue所在的包，即：
import java.util.PriorityQueue;
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常
3. 不能插入null对象，否则会抛出NullPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5.PriorityQueue底层使用了堆数据结构
6. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素
3.2PriorityQueue常用接口介绍
1 构造
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());
}2. 插入/删除/获取优先级最高的元素
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("优先级队列不为空");
}
}
注意默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器
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());
}
}3.3 Topk问题
解法一： 把数组排序，取出前K个最大或者最小
解法二：把所有数据放到优先级队列当中，前K个最小使用小根堆，前K个最大使用大根堆
出队K次
但以上两种办法当遇到数据非常大时，效率会变低
下面介绍效率更高的方法：
解法三：
前K个最大值：
1.建立K值大小的小根堆 2.遍历后面数据 3. 一 一与堆顶比较
如果必堆顶的数值大，说明这个堆顶数值不符合前K个最大数值要求，需要删除，然后将与堆顶比较的数插入到小根堆当中
如果这个数比堆顶数值小，继续遍历；
public int[] maxestK(int[] array ,int k){
int[] ret = new int[k];
if(array == null|| k<=0) return ret;
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
for(int i =0;i < k;i++){
priorityQueue.offer(array[i]);
}
for (int i = k; i < array.length ; i++) {
int top = priorityQueue.peek();
if(array[i] > top){
priorityQueue.poll();
priorityQueue.offer(array[i]);
}
}
for (int i = 0; i < k; i++) {
ret[i] = priorityQueue.poll();
}
return ret;
}前K个最小值:
建立K值大小的大根堆，需要用到比较器
遍历后面的数据，一 一与堆顶数进行比较，如果比它大继续遍历，如果比它小，说明堆顶这个值不符合要求，删除它，插入新的数值，然后继续遍历数值
class IntCmp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}
public int[] smallestK(int[] array ,int k){
int[] ret = new int[k];
if(array == null|| k<=0) return ret;
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());
for(int i =0;i < k;i++){
priorityQueue.offer(array[i]);
}
for (int i = k; i < array.length ; i++) {
int top = priorityQueue.peek();
if(array[i] < top){
priorityQueue.poll();
priorityQueue.offer(array[i]);
}
}
for (int i = 0; i < k; i++) {
ret[i] = priorityQueue.poll();
}
return ret;
}
}如果找第k大的元素（即前K个大的数值里最小的），建立小根堆，与上面找前K个大的元素一致，最后形成的小根堆的堆顶元素就是第K大的元素。
同理找第K小的元素也是如此。
4 堆的应用
4.1 堆排序
1. 升序
建大根堆 利用堆删除思想进行排序
private void shiftDown(int parent,int usedSize){//da
int child = 2*parent +1;
while(child < usedSize){
if(child+1 < usedSize && elem[child] < elem[child+1]){
child++;
}
if(elem[parent] < elem[child]){
swap(child,parent);
parent = child;
child = 2*child+1;
}else{
break;
}
}
}
public void heapSort(){
int end = usedSize -1;
while(end > 0){
swap(0,end);
shiftDown(0,end);
end--;
}
} 2.降序
建小堆，利用删除思想进行排序