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。

完！