目录
一. 优先级队列
1.1 概念
二. 优先级队列的模拟实现
2.1 堆的概念
2.2 堆的存储方式
2.3 堆的创建
2.3.1 堆向下调整
2.3.2 堆的创建
2.3.3 建堆的时间复杂度
2.4 堆的插入与删除
2.4.1 堆的插入
2.4.2 堆的删除
常见习题：
一. 优先级队列
1.1 概念
前面介绍过队列，
队列是一种先进先出
(FIFO)
的数据结构
，但有些情况下，
操作的数据可能带有优先级，一般出队
列时，可能需要优先级高的元素先出队列
，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。
在这种情况下，
数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象
。这种数据结构就是优先级队列
(Priority Queue)
。
二. 优先级队列的模拟实现
JDK1.8
中的
PriorityQueue
底层使用了堆这种数据结构
，而堆实际就是在完全二叉树的基础上进行了一些调整。
2.1 堆的概念
如果有一个
关键码的集合
K = {k0
，
k1
，
k2
，
…
，
kn-1}
，把它的所有元素
按完全二叉树的顺序存储方式存储在一
个一维数组中
，并满足：
Ki <= K2i+1
且
Ki<= K2i+2
(Ki >= K2i+1
且
Ki >= K2i+2) i = 0
，
1
，
2…
，则
称为小堆
(
或大堆)
。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
2.2 堆的存储方式
从堆的概念可知，
堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储
，
注意：对于
非完全二叉树，则不适合使用顺序方式进行存储
，因为为了能够还原二叉树，
空间中必须要存储空节
点，就会导致空间利用率比较低
。
将元素存储到数组中后，可以根据二叉树的性质
对树进行还原。假设
i
为节点在数组中的下标，则有：
如果
i
为
0
，则
i
表示的节点为根节点，否则
i
节点的双亲节点为
(i - 1)/2
如果
2 * i + 1
小于节点个数，则节点
i
的左孩子下标为
2 * i + 1
，否则没有左孩子
如果
2 * i + 2
小于节点个数，则节点
i
的右孩子下标为
2 * i + 2
，否则没有右孩子
2.3 堆的创建
2.3.1 堆向下调整
对于集合
{ 27,15,19,18,28,34,65,49,25,37 }
中的数据，先将其创建成一棵树, 观察是否满足堆的性质
仔细观察上图后发现：
根节点的左右子树已经完全满足小根堆的性质，因此只需将根节点向下调整好即可
。
向下过程
(
以小根堆为例
)
：
1. 让parent标记需要调整的节点，child标记parent的左孩子 ( 注意： parent 如果有孩子一定先是有左孩子 )2. 如果 parent 的左孩子存在，即 :child < size ， 进行以下操作，直到 parent 的左孩子不存在
- parent右孩子是否存在，存在找到左右孩子中最小的孩子，用child进行标记
- 将parent与较小的孩子child比较，如果： parent小于较小的孩子child，调整结束 , 否则：交换parent与较小的孩子child，交换完成之后，可能导致下面的子树不满足堆的性质，因此需要继续向下调整，即parent = child；child = parent*2+1; 然后继续2步骤。
参考代码:
//向下调整(小根堆)
private void siftDownSmallHeap(int parent ,int end){
int child = 2 * parent + 1;//child==左孩子
while(child < end){
//如果有右孩子并且右孩子是左右孩子中最小的
if(child + 1 < usedSize && elem[child] > elem[child + 1]){
child++;//child==右孩子
}
//如果孩子小于父母, 不满足小根堆的性质, 则交换
if(elem[parent] > elem[child]){
swap(child,parent);//交换
parent = child;//向下调整
child = 2*parent+1;//向下调整
}else{
break;
}
}
}
//向下调整(大根堆)
private void siftDownBigHeap(int parent ,int end){
int child = 2 * parent + 1;//child==左孩子
while(child < end){
//如果有右孩子并且右孩子是左右孩子中最大的
if(child + 1 < usedSize && elem[child] > elem[child + 1]){
child++;//child==右孩子
}
//如果孩子大于父母, 不满足大根堆的性质, 则交换
if(elem[parent] > elem[child]){
swap(child,parent);//交换
parent = child;//向下调整
child = 2*parent+1;//向下调整
}else{
break;
}
}
}
时间复杂度分析：
最坏的情况
即图示的情况，
从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为O(
)
2.3.2 堆的创建
注意：
在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整, 不然会有增加许多不必要的调整, 因此在创建堆的时候, 需要从最后一个结点开始调整
对于普通的序列 { 1,5,3,8,7,6 }, 假设要创建大根堆
第一步: 右树, 3 < 6 , 交换3 6
第二步: 左树, 7 8 最大值8 > 5 , 交换5 8
第三步:根, 6 8 最大值8 > 1, 交换8 1
第三步完成后, 破坏了左子树的大根堆结构, 如图所示:
第四步: 所以接下来就是向下调整时需要做的工作, 即重新对阴影部分进行构造堆, 递归的进行向下调整
第五步:完成
参考代码:
/*
最后一个结点:usedSize-1
最后一个结点的父亲: (usedSize-1-1)/2
*/
public void createBigHeap(){
for(int parent = (usedSize-1-1)/2;parent >=0;parent--){//从最后一个结点的父亲结点开始判断是否需要调整
siftDownBigHeap(parent,usedSize);//调用大根堆对应的向下调整方法
}
}2.3.3 建堆的时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明
(
时间复杂度本来看的就是近似值，多几个节点不影响最终结果)
：
因此：
建堆的时间复杂度为
O(N)
2.4 堆的插入与删除
2.4.1 堆的插入
堆的插入总共需要两个步骤：
1.
先将元素放入到底层空间中
(
注意：空间不够时需要扩容
)
2.
将最后新插入的节点向上调整，直到满足堆的性质
参考代码:
//插入元素
public void offer(int val){
//判断是否满, 满则扩容
if(isFull()){
this.elem = Arrays.copyOf(elem,elem.length*2);
}
//插入元素到最后
elem[usedSize] = val;
usedSize++;
//向上调整
siftUp(usedSize-1);
}
//向上调整(大根堆)
private void siftUp(int child){
int parent = (child-1)/2;
while(child > 0){
if(elem[child] > elem[parent]){
swap(child,parent);
child = parent;
parent = (child-1)/2;
}else{
break;
}
}
}
private boolean isFull(){
return elem.length == usedSize;
}
2.4.2 堆的删除
注意：堆的删除一定删除的是堆顶元素。
具体如下：
1.
将堆顶元素对堆中最后一个元素交换
2.
将堆中有效数据个数减少一个
3.
对堆顶元素进行向下调整
参考代码:
public int poll(){
int tmp = elem[0];
swap(0,usedSize-1);
usedSize--;
siftDownBigHeap(0,usedSize);
return tmp;
}常见习题：
1. 下列关键字序列为堆的是 :(A)A: 100,60,70,50,32,65 B: 60,70,65,50,32,100 C: 65,100,70,32,50,60D: 70,65,100,32,50,60 E: 32,50,100,70,65,60 F: 50,100,70,65,60,32解:堆要满足大根堆或小根堆A:满足大根堆,选A
2. 已知小根堆为 8,15,10,21,34,16,12 ，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是 (C)A: 1 B: 2 C: 3 D: 4解:小根堆删除后:
比较选C
3. 最小堆 [0,3,2,5,7,4,6,8], 在删除堆顶元素 0 之后，其结果是 (C)A: [3 ， 2 ， 5 ， 7 ， 4 ， 6 ， 8] B: [2 ， 3 ， 5 ， 7 ， 4 ， 6 ， 8]C: [2 ， 3 ， 4 ， 5 ， 7 ， 8 ， 6] D: [2 ， 3 ， 4 ， 5 ， 6 ， 7 ， 8]解:小根堆删除后:
向下调整:选C
