数据结构（java实现）——优先级队列，堆

---

优先级队列

前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该种场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

堆

优先级队列是一种概念的数据结构，我们使用堆这种具体的数据结构来实现它。

堆的概念

堆是一棵以数组方式存储的完全二叉树。
存储方式按照层序遍历的方式存储。

堆又分为小根堆，大根堆两种：
大根堆是指所有的节点值比其左右节点值都大（左右节点在的情况下）。
大根堆的根节点是最大值
小根堆是指所有的节点指比其左右节点值都小（左右节点在的情况下）。
小根堆的根节点是最小值

堆的模拟实现

我们以大根堆举例：
实现的方法与属性：

public class PriorityQueue {public int[] elem;public int usedSize;//初始化长度为10的数组public PriorityQueue() {elem = new int[10];}//创建建堆public void createHeap(int[] array) {}private void shiftDown(int root,int len) {}// 入堆：仍然要保持是大根堆public void push(int val) {}private void shiftUp(int child) {}//判断堆是否满public boolean isFull() {}//每次删除的都是优先级高的元素,删除后任是大根堆public void pollHeap() {}//判断堆是否为空public boolean isEmpty() {}// 获取堆顶元素public int peekHeap() {}
}

创建堆

创建堆的方式有两种，一种是向上调整，向下调整。
我们依次介绍：
向下调整：根据一组数据创建成一个大根堆，以{1，5，3，8，7，6}举例：

 所以向下调整的含义即每一棵子树均从根节点开始向下比较。

实现思想：

1. createHeap思路：

先将数组拷贝进成员数组中（注意看长度是否够）。
我们从最后一棵子树的根节点开始调用shiftDown方法向上一棵一棵树的调整为大根堆。
2. shiftDown思路：

将当前传入的根节点与他的孩子节点将最大值选出作为根。
然后将根变成孩子节点再次调整。
注意挑选最大值的时候要判断不能让下标越界。

public void createHeap(int[] array) {if(elem.length < array.length){elem = Arrays.copyOf(elem, elem.length * 2);}for (int i = 0; i < array.length; i++){elem[i] = array[i];usedSize++;}for (int root = (usedSize -1 -1) / 2; root >= 0 ; root--) {siftDown(root,usedSize);}}private void siftDown(int root,int len) {int child = root * 2 + 1;while (child < len){//寻找孩子节点的大值if(child + 1 < len && elem[child] < elem[child + 1]){child++;}if(elem[root] < elem[child]){swap(elem,root,child);root = child;child = root * 2 + 1;}else {break;}}}//交换函数private void swap(int[] array,int x,int y){int tmp = array[x];array[x] = array[y];array[y] = tmp;}

向上调整：
向上调整的思路即以入堆的方式，将每一个元素依次插入堆中。

 我们从最后一棵节点开始于其子树的根节点比较，这个向上比较的过程，我们称为向上调整。

代码实现：

public class Test {public static void main(String[] args) {int [] array = {27,15,19,18,28,34,65,49,25,37};TestHeap testHeap = new TestHeap();for (int i = 0; i < array.length; i++) {testHeap.push(array[i]);}}
}

 具体的入堆代码，看下面。

入堆

代码思路：

1. 先判断堆是否已经满了，满了要扩容。
2. 在堆最后存入该元素，然后与父亲节点相比较，比父亲节点大就交换，直到到根节点或者比父亲节点小为止。

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

判满

public boolean isFull() {return usedSize == elem.length;}

删除

实现思想：

1. 先判断堆是否为空，为空直抛空指针异常。
2. 我们先将堆顶和堆尾交换，然后向下调整一次。
3. usedSize减1。

public void pollHeap() throws NullPointerException {if (isEmpty()) {throw new NullPointerException();}swap(elem,0,usedSize-1);siftDown(0,usedSize);usedSize--;}

判空

public boolean isEmpty() {return usedSize == 0;}

获取栈顶元素

如果堆为空，抛空指针异常，没有直接返回堆顶元素。

public int peekHeap() throws NullPointerException {if (isEmpty()) {throw new NullPointerException();}return elem[0];}

创建堆两种方式的时间复杂度

向下调整的时间复杂度为O（N）：

当计算复杂度时，只计算替换次数即可，不需要计算每次替换中语句的执行数目，因为到最后计算时，前面的系数均会变为1.
向上调整的时间复杂度为O(N*logN)：

堆排序

假设我们要将一组数据在一个数组中从小到大排序，那我们要创建大根堆，还是小根堆？
如果要创建小根堆，我们只能保证堆顶元素为最小值，但是不能保证，左边的元素比右边的元素大，这不是小根堆的特性。
所以我们要创建大根堆

public void heapsort(){
//此方法是在创建大根堆之后的堆排序方法int end = Usedsize-1;while(end>0){swap(elem,0,end);siftDown(0,end);end--; }
}

java提供的PriorityQueue类

基本的属性

1. DEFAULT_INITIAL_CAPACITY 为申请初始化空间大小的默认值
2. queue为底层使用的数组
3. size指数组中有效元素的个数
4. comparator指类使用的比较器

关于PriorityQueue类的三个构造方法

这三个构造方法均调用了自己的第四个构造方法

所以我们直接看第四个构造方法实现逻辑：如果申请的空间大小小于1，则直接报异常，当大于等于1时，为优先级队列申请第一个参数数值大小的空间，并采用第二个参数的比较器。

关于PriorityQueue类中，入堆方法是怎样实现的？

PriorityQueue注意事项

1. PriorityQueue中放置的元素必须是可以比较的，即实现了comparable接口的类,否则会报ClassCastException异常。
2. 不能插入null对象，否则会报NullPointerException异常。
3. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容。

堆的一个oj题

Topk问题，最小的k个数
这个题有三种做法：

1. 直接进行整体堆排序。

2. 直接建立一个小根堆，然后依次出堆顶元素，再调整

3. 把前k个元素创建为大根堆，遍历剩下的N-K个元素，和栈顶元素比较，如果比栈顶元素小，则删除栈顶元素，将此元素入堆。
   此种算法的时间复杂度为：前k个元素创建一个大根堆的时间复杂度加上后面N-k个元素进行入堆操作的时间复杂度==klogk+(N-k)*logk == Nlogk
   采用第三种做法：

class Clmp implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}
class Solution {public int[] smallestK(int[] arr, int k) {int [] ret = new int[k];if(arr ==null||k==0){return ret;}PriorityQueue<Integer>priorityQueue = new PriorityQueue<>(k,new Clmp());//我们需要创建一个大根堆//将前k个元素插入到优先级队列中去for (int i = 0; i < k; i++) {priorityQueue.offer(arr[i]);}
//然后遍历剩余的元素for (int i = k; i <arr.length ; i++) {if(arr[i] < priorityQueue.peek()) {//则将两者的值进行交换priorityQueue.poll();priorityQueue.offer(arr[i]);}}ret = new int[k];for (int i = 0; i < k; i++) {ret[i]  = priorityQueue.poll();}return ret;}
}