1.优先级队列

1.1概念

队列是一种先进先出的数据结构。但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的的元素先出队列。这种情况下，数据结构提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象，这种数据结构称之为优先级队列（Priority Queue）

2.优先级队列的模拟实现

JDK1.8中的PriorityQueue底层使用了堆的数据结构，而堆实际就是在完全二叉树的基础之上进行了一些元素的调整。
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
在这里插入图片描述

2.1堆的存储方式

堆是一颗完全二叉树，因此可以层序的规则采用顺序的方式来高效存储。
在这里插入图片描述
注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。
将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：

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

2.2堆的创建

在这里插入图片描述

public class TestHeap {public int[] elem;public int usedSize;//有效的数据个数public static final int DEFAULT_SIZE = 10;public TestHeap() {elem = new int[DEFAULT_SIZE];}public void initElem(int[] array){for(int i = 0;i < elem.length;i++){elem[i] = array[i];usedSize++;}}public void createHeap(){for(int parent = ((usedSize-1)-1)/2;parent >= 0;parent--){shiftdown(parent,usedSize);}}//parent:表示每棵子树的节点//len表示没课字数调整的结束位置，不能大于lenpublic void shiftdown(int parent,int len){int  child= parent * 2 +1;//孩子的下标必须小于有效长度，保证有左孩子while(child < len){//child+1 < len保证有右孩子if(child+1 < len && elem[child] < elem[child +1]){child ++;}if(elem[child]>elem[parent]){int tmp = elem[child];elem[child] = elem[parent];elem[parent] = tmp;parent = child;child = 2 *parent + 1;}else{break;}}}
}

在这里插入图片描述

这是大堆的情况下。那么我们如何改为小根堆呢？很简单，只需要改变两个符号。

2.3建堆的复杂度

在这里插入图片描述
综上：建堆的时间复杂度为O(n)

2.4堆的插入和删除

想要向堆中插入元素，我们可以先插入到最后一个位置上。在对其进行大根堆调整。

public void offer(int val){//如果满了就扩容if(isFull()){elem = Arrays.copyOf(this.elem,2*this.elem.length);}elem[usedSize] = val;usedSize++;//调整为大根堆shiftup(usedSize-1);}public void shiftup(int child){int parent = (child-1)/2;while(parent >= 0){if(elem[child] > elem[parent]){int tmp = elem[child];elem[child] = elem[parent];elem[parent] = tmp;child = parent;parent = (child -1)/2;}else{break;}}}public boolean isFull(){return usedSize == elem.length;}

在这里插入图片描述

在这里插入图片描述
其次，我们来看堆的删除：
堆的删除一定删除的是堆顶元素。（删除中间元素无意义）

public int pop(){if(isEmpty()){throw new isEmptyExpection("堆空异常!");}int tmp = elem[0];elem[0] = elem[usedSize-1];elem[usedSize-1] = tmp;usedSize--;shiftdown(0,usedSize);return tmp;}public boolean isEmpty(){return usedSize == 0;}