数据结构-优先级队列

一，堆

1，一棵完全二叉树，顺序存储（数组）层序遍历。非完全二叉树则不用数组存储，因为空间利用率低

2，分为小根堆（每棵子树都是小根堆）和大根堆。以大根堆举例，一整棵树的每一棵子树的孩子节点都小于父亲节点。

3，孩子下标2i+1和2i+2，父亲节点的下标（i-1）/2

二，用堆实现优先级队列：

首先优先级队列的本质是一个数组，因此定义一个数组，和一个记录数组中有多少元素整型变量useSize

1，将一个数组调整为大根堆

我们需要求出最后一个子节点的父节点，然后向前遍历，将每一个父节点就进行向下调整。

向下调整：需要知道需要调整的父节点的下标和调整的范围（如果是建立大根堆，调整的范围就是到最后一个下标），知道父亲节点后求出左子节点，然后判断是否有右子节点，如果有那么判断array[child+1]与array[child]的大小关系，如果关系是大于，那么child++，这样保证child所指向的是较大的子孩子。然后将较大的子孩子和父节点的值进行比较，如果孩子节点大于父亲节点，那么两者交换，因为如果两者交换的话，会影响被交换为子节点的节点作为父亲节点时，与它自己的子节点的大小关系，所以交换后要parent=child; child=parent*2+1;然后再次重复循环上述操作，直到孩子节点是越界，则代表调整完毕。但如果父亲节点大于孩子节点就可以直接跳出循环了，因为父子节点之间不需要交换，而子节点以下的节点本身就是调整好的所以不需要再次调整，直接跳出循环即可。

private void swap(int i,int j){     int tmp=elem[i];     elem[i]=elem[j];     elem[j]=tmp; }  public void siftDown(int parent,int end){     int child=parent*2+1;     while (child<end){         if (child+1<end && elem[child]<elem[child+1]){             child++;         }         if (elem[child]>elem[parent]){             swap(child,parent);             parent=child;             child=2*parent+1;         }else {             break;         }     } }  public void createHeap(){     for (int parent =(useSize-1-1)/2 ; parent >=0; parent--) {         siftDown(parent,useSize);     } }

向下调整的时间复杂度是O(log2(n))

建堆的时间复杂度为O(N)

2，添加元素offer

首先判断是否满了，如果满了，就需要进行扩容。我们将添加的元素放到数组的最后，这时就需要将最后一个数值进行调整，使其实现大根堆。这是我们就需要向上调整。

向上调整：

我们得到子节点的下标后，推算出父亲节点的下标，然后对父亲节点和子节点进行比较。如果子节点大于父亲节点，那么子节点和父亲节点的值进行交换。然后将子节点的下标等于父亲节点的下标，父亲节的下标重新根据子节点进行计算，从而得到新的子节点和父亲节点，然后再次进行比较，循环上述行为，直到父亲节点大于0时结束。在上述子结点的值与父亲节点的值比较大小时，如果不大于则直接break跳出循环。

public void offer(int val){    if (isFull()){        elem= Arrays.copyOf(elem,2*elem.length);    }    elem[useSize]=val;    useSize++;    siftUp(useSize-1); } private void siftUp(int child){    int parent=(child-1)/2;    while (parent>=0){        if (elem[child]>elem[parent]){            swap(child,parent);            child=parent;            parent=(child-1)/2;        }else {            break;        }    } }

总结：

时间复杂度：O（log2(n)）

3，删除一个元素

首先这是一个队列，所以符合先进先出的原则，所以删除时，最先删除的是首元素。这时我们可以将首元素和尾元素进行交换，然后useSize减减，这时首元素不符合大根堆的原则，所以将首元素进行向下调整。

public int poll(){     if (isEmpty()){         return -1;     }     int old=elem[0];     swap(0,useSize-1);     useSize--;     siftDown(0,useSize);     return old; }

总结：

时间复杂度：O（log2(n)）

4，堆排序

大根堆下标为0的元素一定是最大的，所以可以将第一个元素和最后一个下标的元素交换，然后将第一个元素向下调整重新调整为大根堆，调整的终点是前一次调整的数组长度-1（已经选出了最大的元素，现在需要在剩余的元素中找到第二大的，所以向下调整大范围不包括已经排好序的数据），然后然后循环上述行为。使数组中的每一个元素都得到调整从而就可以得到顺序了。

public void heapSort(){     int endIndex=useSize-1;     while (endIndex>0){         swap(0,endIndex);         siftDown(0,endIndex);         endIndex--;     } }

总结：

时间复杂度：O（n*log2(n)）

空间复杂度：O（1）

三，优先级队列

1，概括：

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

2，.ClassCastException异常

当优先级队列中放置的元素是不能进行比较时，会抛出异常。由下图可知，再调用offer方法时会调用到siftUpComparable（）方法，这个方法需要元素之间进行比较，所以会抛出ClassCastException异常

3,NullPointerException异常

不能插入null，会抛出NullPointerException异常

4，优先级队列默认构建的是小根堆

5，删除和添加元素时间复杂度都是O（log2(n)）

6，构造函数

优先级队列有三种构造函数，分别为无参（默认容量为11），有参，和参数为优先级队列的对象。

7，比较器（大根堆）

默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器。直接实现Comparator接口，然后重写该接口中的compare方法即可。

class InCmp implements Comparator<Integer>{     @Override     public int compare(Integer o1, Integer o2) {         return o2.compareTo(o1);     }//大根堆

PriorityQueue<Integer>priorityQueue=new PriorityQueue<>(new InCmp());

四，练习

找到前k个最小的数字

方法一：

将所有元素均放到优先级队列中，然后poll前三k，并将前k个放到临时数组中。

public int[]smallestK(int [] arr,int k){     PriorityQueue<Integer> queue=new PriorityQueue<>();     for (int i = 0; i < arr.length; i++) {         queue.offer(arr[i]);     }     int[] tmp=new int[k];     for (int i = 0; i <k; i++) {         tmp[i]=queue.poll();     }     return tmp; }

这种方法的思维逻辑较为简单，但是时间复杂度比较大，效率不高。因为你需要将每一个元素添加到优先级队列中，然后删除k个元素，而添加和删除的时间复杂度均为O(log2(n))，所以这种方法的时间复杂度为O((n+k)*log2(n)).

方法二：（优化）

当要寻找前k个较小的数字时，可以建立一个大小为k的大根堆优先级数列。将数组中前k个放到优先级队列中，然后数组从k处开始向后遍历，当优先级队列的首元素比数组中的元素小大时，将有首元素弹出，然后添加数组中的这个元素。循环结束后，则优先级队列中的元素就是前k个较小的数字，所以将优先级队列里面的元素弹出放到临时数组中，并返回。

这时，之间复杂度为：O（nlog2（n））

public int[]smallestK2(int [] arr,int k){     int[] tmp=new int[k];     if (k==0){         return tmp;     }     PriorityQueue<Integer> maxHead=new PriorityQueue<>(new InCmp());     //1，先把看个元素放到元素中     for (int i = 0; i <k; i++) {         maxHead.offer(arr[i]);     }     //2，遍历剩下的元素     for (int i = k; i < arr.length; i++) {         int val=maxHead.peek();         if (val>arr[i]){             maxHead.poll();             maxHead.offer(arr[i]);         }     }      for (int i = 0; i < k; i++) {         tmp[i]=maxHead.poll();     }     return tmp; } 

当然，这种方法也可以寻找第k大的数字或者第k小的数字，只需要注意如果想找大的……（第k个数字/前k个较大的），就需要建立一个小根堆，反之，则需要建立一个大根堆