【数据结构七】堆与PriorityQueue详解

堆

         在Java中有一种数据结构基于队列，并保证操作的数据带有优先级，该数据结构应该提供了两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。它的底层使用了堆这种数据结构，堆其实就是在二叉树的基础上进行了一些调整。

1.什么是堆

堆的概念：

         堆能把它的所有元素按照完全二叉树的方式存储在一个一维数组中，并保证每次出队列的元素都是这些元素中的最大值或最小值。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

•  堆中某个节点的值总是不大于或不小于其父节点的值；
•  堆总是一颗完全二叉树

                                                                 完全二叉树 

                                                                一般二叉树 

    堆的存储方式：

             前面过二叉树的存储方式有两种，数组或链表，因为数组存储的方式在二叉树不是完全二叉树的情况下，有明显的对内存的浪费，所以我们当时选择了链表的方式，但是堆肯定是一颗完全二叉树，在这里我们利用层序的规则采用数组来高效存储。

• 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
• 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
• 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

2.优先级队列（堆）的实现

我们以创建一个小根堆为例，如何创建一个小根堆呢？

            其实这是一个不断向下调整的过程，定义parent等于二叉树的根节点，同过让它不断与孩子节点进行比较和交换位置，将这样的过程重复就能得到一个堆了，具体过程如下：

1. 让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)
2. 如果parent的左孩子存在，即:child < size， 进行以下操作，直到parent的左孩子不存在

1. parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标记
2. 将parent与较小的孩子child比较，如果：

• parent小于较小的孩子child，调整结束
• 否则：交换parent与较小的孩子child，交换完成之后，parent中大的元素向下移动，可能导致子树不满足对的性质，因此需要继续向下调整，即parent = child；child = parent*2+1; 然后继续2。

 堆的插入：

堆的插入总共需要两个步骤：
1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)
2. 将最后新插入的节点向上调整，直到满足堆的性质

 

堆的删除： 

    堆的删除一定删除的是堆顶元素。我们可以通过以下步骤进行删除操作：

1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整
 

由上述可知，创建一个自己的堆重点需要手写向上调整，和向下调整的方法，解决了这两个方法，堆的操作便可迎刃而解了。下面的优先级队列的代码实现：

public class MyPriorityQyueue {public int[] array;public int usedSize;public MyPriorityQyueue(){this.array=new int[10];}public void initArray(int[] arr){for(int i=0;i<arr.length;i++){array[i]=arr[i];usedSize++;}}public void createHeap() {for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {shiftDown(parent,usedSize);}}public void offer(int val) {if(isFull()) {//扩容array = Arrays.copyOf(array,2*array.length);}array[usedSize++] = val;//11//向上调整shiftUp(usedSize-1);//10}public int pop() {if(isEmpty()) {return -1;}int ret=array[0];swap(array,0,usedSize-1);usedSize--;shiftDown(0,usedSize);return ret;}public int peek(){if(isEmpty()) {return -1;}return array[0];}public boolean isEmpty() {return usedSize == 0;}private void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}public boolean isFull() {return usedSize == array.length;}private void shiftDown(int parent,int len){int child =2*parent+1;while(child<len){if(child+1<len&&array[child]<array[child+1]){child++;}if(array[child]<array[parent]){int tmp=array[child];array[child]=array[parent];array[parent]=tmp;parent=child;child=2*parent+1;}else{break;}}}private void shiftUp(int child) {int parent = (child-1)/2;while (child > 0) {if(array[child] < array[parent]) {int tmp = array[child];array [child] = array[parent];array[parent] = tmp;child = parent;parent = (child-1)/2;}else {break;}}}
}

3.PriorityQueue的使用

     PriorityQueue是Java对堆的一个实现类，继承了Queue接口。

1. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
2. 不能插入null对象，否则会抛出NullPointerException
3. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
4. 插入和删除元素的时间复杂度为O(log2N)
5. PriorityQueue底层使用了堆数据结构
6. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素

在Java中重写comparator方法可实现小根堆到大根堆的转换：

A=new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
});

常用方法：
 

函数名	功能介绍
boolean offer(E e)	插入元素e，插入成功返回true，e不能为空，会自动扩容。时间复杂度O（log2N）。
E peek()	获取优先级最高的元素。
E poll()	移除优先级最高的元素并返回。
int size()	获取有效元素的个数
void clear()	清空
boolean isEmpty()	检测优先级队列是否为空。

优先级队列的扩容说明：
如果容量小于64时，是按照oldCapacity的2倍方式扩容的
如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容

4.优先级队列的应用

利用堆排序的思想解决TOP-K问题：

在数据量极大的情况下求数据集合中前K个最大的元素或者最小的元素。

           因为此时数据太大，无法一次性全部加载到内存中，不能使用一般的排序方法来进行求解了，最佳方式用堆求解，思路如下：

1.用数据集合中前K个元素来建堆

                   前k个最大的元素，则建小堆

                   前k个最小的元素，则建大堆

2.用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。