java数据结构_优先级队列（堆）_6.1
1. 优先级队列
1.1 概念
队列是一种先进先出（FIFO）的数据结构，但某些情况下，操作的数据可能带有优先级，一般出队列的时候，可能需要优先级高的元素出队列，那这种情况，再用普通的队列结构，就不合适了。
在这种情况下：数据结构应该提供两个最基本的操作，一个是返回最高优先级队列，一个是添加新的对象，这种数据结构就是优先级队列。
2. 优先级队列的模拟实现
JDK1.8中的PriorityQueue底层使用了 堆 这种数据结构，而堆的底层实际就是在完全二叉树的基础上进行了一些调整。
2.1 堆的概念
堆分为小根堆和大根堆
首先，无论是小根堆 还是 大根堆，两者都是完全二叉树，其区别是堆序性，小根堆中的任意一个结点，其值都小于或等于它的子树的值。而大根堆中的任意一个结点，其值都大于或等于它的子树的值。
2.2 堆的存储方式
堆是一棵完全而擦函数，可以用层序的规则顺序存储
对于非完全二叉树，则不适合使用顺序方式存储，因为空间中需要存储空结点，导致空间利用率降低。
回忆完全二叉树性质：假设 i 为结点在数组中的下标，则有：
- 如果 i 为 0，则 i 表示的结点为根结点，否则 i 结点的双亲结点为(i - 1) / 2
- 如果结点有左孩子，则左孩子的下标为 2 * i + 1
- 如果结点有右孩子，则右孩子的下标为 2 * i + 2
2.3 堆的创建
如下图，将一棵普通的完全二叉树，调整为了大根堆，其方法为，找到最下面的一棵子树，然后将其根结点与子树进行比较，调整每一棵子树根结点的位置，该方法称为向下调整。
先进行堆的相关变量创建，及其初始化：
接下来是创建堆的方法：
找到倒数第一个非叶子结点，从该节点开始向前一直到祖先结点，根结点向下和子树按照大根堆或者小根堆的性质进行调整。
完全二叉树中，最后一个结点的索引是usedSize - 1，则父亲结点的索引是(usedSize - 1 - 1) / 2
public void createHeap() {
for(int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
shiftDown(parent, usedSize);
}
}向下调整的方法，以大根堆为例：
private void shiftDown(int parent, int usedSize) {
//左孩子下标
int child = (2 * parent) + 1;
while(child < usedSize) { //确保左孩子不会越界
//child + 1 < usedSize 确保右孩子不会越界
//elem[child] < elem[child + 1] 右孩子的值大于左孩子的值
if(child + 1 < usedSize && elem[child] < elem[child + 1]) {
//child一定是左右孩子中值较大的下标
child++;
}
//孩子下标对应的值大于根结点的值，大根堆 进行交换
if(elem[child > elem[parent]) {
swap(child, parent);
//完成一次父结点和子结点的交换后，更行当前处理的结点的位置
parent = child;
child = parent * 2 + 1; //再次找到新的父结点的左孩子进行比较
} else {
break; //已经是大根堆
}
}
}
private void swap(int i, int k) {
int tmp = elem[i];
elem[i] = elem[k];
elem[k] = elem[tmp];
}测试符合预期
创建堆的时间复杂度：
堆的本质是完全二叉树，满二叉树是一种特殊的完全二叉树，为了简化过程，可以用满二叉树来进行证明（时间复杂度求的就是近似值且是最坏情况，所以多几个结点并不会影响最后的结果）
推导如下：
2.4 堆的插入
插入要考虑两件事：
1. 将元素往哪里放？（堆是否满？ -- > 扩容）
2. 放进去怎么放到合适的位置？
将新插入的元素放入到最底层的空间中，空间不够的时候需要扩容，然后将最后插入的结点按照堆的性质向上调整
于是有代码：
public void offer(int val) {
if(isFull()) {
this.elem = Arrays.copyOf(elem, elem.length * 2);
}
this.elem[usedSize] = val;
shiftUp(usedSize);
usedSize++;
}
public void shiftUp(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;
}
}
}
public boolean isFull() {
return usedSize == elem.length;
}测试符合预期：
2.5 堆的删除
注意：堆的删除一定是删除栈顶元素。
步骤：
- 将堆顶部元素与堆中最后一个元素进行交换
- 将堆中有效数据个数(usedSize)减少一个
- 对堆顶元素进行向下调整
于是有代码：
public int poll() {
int ret = elem[0];
swap(0, usedSize - 1);
usedSize--;
shiftDown(0,usedSize);
return ret;
}测试符合预期：
练习题：
已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是()
A: 1 B: 2 C: 3 D:
堆的模拟图如下
删除关键字8，即是8与12进行交换，usedSize--，12向下调整
第一次比较 15 和 10 进行比较 --> 10较小
第二次比较 10 和 12 进行比较 --> 10较小
第三次比较 12 和 16进行比较 --> 12较小
所有一共有三次比较，选C。
完！