【数据结构】堆，优先级队列

堆

如果有一个集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质

• 堆逻辑结构上是一棵完全二叉树。
• 堆上的节点一定不大于（大根堆）或者不小于（小根堆）父亲节点。

大根堆的模拟实现

使用代码来实现一个大根堆。

接口实现

接口成员方法。

public class PriorityQueue {public int[] elem;public int usedSize;public PriorityQueue() {}//建堆public void createHeap(int[] array) {}/*** @param root 是每棵子树的根节点的下标* @param len  是每棵子树调整结束的结束条件* 向下调整的时间复杂度：O(logn)*/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() {}
}

构造方法

在构造方法中构建为长度10的数组。

public PriorityQueue() {elem = new int[10];}

建堆

createHeap思路：

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

shiftDown思路：

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

 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--) {shiftDown(root,usedSize);}}/*** @param root 是每棵子树的根节点的下标* @param len  是每棵子树调整结束的结束条件* 向下调整的时间复杂度：O(logn)*/private void shiftDown(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;}

入堆

代码思路：

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

	 /*** 入堆：仍然要保持是大根堆* @param val*/public void push(int val) {if(isFull()){elem = Arrays.copyOf(elem, elem.length*2);}elem[usedSize] = val;shiftUp(usedSize);usedSize++;}private void shiftUp(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;}}}

判满

这个方法直接使用成员变量usedSize和数组长度判断即可。

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

删除

代码思路：

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

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

判空

这个方法直接使用成员变量usedSize是否为0就行。

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

获取堆顶元素

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

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

Java中的PriorityQueue

在Java中使用集合类PriorityQueue来表示优先级队列，其底层是一个小根堆。

实现的接口

构造方法

提供了以下3种构造方法：

方法	方法用途介绍
PriorityQueue()	创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)	创建一个初始容量为initialCapacity的优先级队列，注意initialCapacity不能小于1，否则会抛IllegalArgumentException异常
PriorityQueue(Collection<? extends E> c)	用一个集合来创建优先级队列

常用方法

常用方法如下：

PriorityQueue注意事项

1. 使用要导包import java.util.PriorityQueue;
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常。
3. 不能插入null对象，否则会抛出NullPointerException。
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容。
5. 如果要将PriorityQueue变成一个大根堆，类实现Comparator后重写 compare方法时将比较改为

public int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}

练习

最小k个数