PriorityQueue其本质是一个优先级队列的集合。

1. 优先级队列

那什么是优先级队列呢我们先从它的概念聊起。

概念

前面介绍过队列队列是一种先进先出(FIFO)的数据结构但有些情况下操作的数据可能带有优先级一般出队列时可能需要优先级高的元素先出队列该中场景下使用队列显然不合适比如在手机上玩游戏的时候如果有来电那么系统应该优先处理打进来的电话初中那会班主任排座位时可能会让成绩好的同学先挑座位。在这种情况下数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

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

JDK1.8中的PriorityQueue底层使用了堆这种数据结构而堆实际就是在完全二叉树的基础上进行了一些调整。

问题又来了什么叫做堆呢

2.1 堆

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

这不是很好理解我们来画个图

我用绿色和灰色圈起来的我们将其看为一棵树我们发现这颗树上的根节点的值都大于其左右子节点这样的我们称之为大根堆但如果是每棵树的根节点的值都小于其左右子节点我们称之为小根堆。

堆的性质我们上面已经提到了

1.堆中某个节点的值总是不大于或不小于其父节点的值

2.堆总是一棵完全二叉树。

当然啦从堆的概念可知堆是一棵完全二叉树因此可以层序的规则采用顺序的方式来高效存储。

如上图我们不会存在浪费空间的情况但是如果是一颗非完全二叉树那么就会存在浪费空间的情况

 所以对于非完全二叉树则不适合使用顺序方式进行存储因为为了能够还原二叉树空间中必须要存储空节点就会导致空间利用率比较低。

2.2 堆的创建

对于任意集合中的数据如何将其创建成堆呢

我们只需要象完全二叉树一样去插入然后再对其向下向下调整即可。

具体实现还得看需求需要小根堆则向下调整需要大根堆则向上调整。

我们以向上调整为例

首先先创建一个堆代码如下

public class TestHeap {
    
    public int[] elem;
    public int usedSize;//堆的有效元素数

    public TestHeap() {
        this.elem = new int[10];//初始化一个容量后面还可以扩容
    }
}

2.3 入堆

假设有这么个堆我们需要插入新元素98

 从逻辑结构上看这并不是一个大根堆我们得想办法让98到68的位置上去。此时就发生了向上调整

一次仍然得不到大根堆继续向上调整

 

 再次调整后得到了一个新的大根堆。

动图演示

 那么思路整理好了代码如何去写呢

写代码前我们得知道几个概念

将元素存储到数组中后可以根据二叉树章节的性质对树进行还原。假设i为节点在数组中的下标则有
如果i为0则i表示的节点为根节点否则i节点的双亲节点为 (i - 1)/2
如果2 * i + 1 小于节点个数则节点i的左孩子下标为2 * i + 1否则没有左孩子
如果2 * i + 2 小于节点个数则节点i的右孩子下标为2 * i + 2否则没有右孩子

再PriorityQueue中向上调整传了一个父元素下标和一个E类型的元素我们简单一点只进行调整插入元素后面的方法再写。

 堆的向上调整调整分为如下几步

1. 假设当前插入的元素处节点为孩子那么需要找到他的父亲节点计算公式为 child = (parent - 1) / 2
2. 通过所得到的父亲与孩子都是下标判断二者所代表的值大小假设当前要建大堆如果孩子比父亲大那么就需要交换孩子与父亲的值孩子变成父亲向上更新父亲如果不满足条件则不需要进行调整直接结束循环即可
3. 假设这个新插入的元素节点很大甚至能直接取代堆顶元素根节点那么循环的条件就要设为 孩子 > 0

代码如下

 public void shiftUp(int parent) {
        int child = (parent - 1)/2 ;
        while (child > 0) {
            //找出左右孩子中最大的值与之交换
            if ( elem[child] > elem[parent]) {
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                child = parent;
                parent = (child-1)/2;
            } else {
                break;
            }
        }
    }

 注意

1. 在进行向上调整时正确的找到孩子及其对应父亲是关键
无论是左孩子还是右孩子都可以通过 parent = (child - 1) / 2 来计算父亲
2. 调整的核心是为元素找到合适的位置这个思想很重要
所谓合适的位置就是必须满足原则一成为大堆或小堆

说到这里我们又不得不提一嘴堆的时间复杂度

2.4  堆的时间复杂度

因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个节点不影响最终结果)

 

故此 建堆的时间复杂度为O(N)

写完了向上调整我们入堆的准备工作就结束了可以开始正式入堆。

那么我们的代码就很简单了

思路

1. 第一步当然是需要检查容量是否足够不够的话需要扩容我们写简单一点直接用Arrays.copyOf方法

2. 我们将需要添加进来的元素直接向数组中放入就好

3. 插入元素后它就不一定是一个大根堆了那么我就需要给他向上调整以下即可

创建堆和插入代码

public void createHeap() {
        //为什么不直接减2而需要减1再减1
        //因为usedSize - 1 是数组下标在逻辑上我们从父节点到左子节点需要减1 / 2
        for (int parent = (usedSize-1-1) / 2; parent >= 0; parent--) {
            shiftUp(parent,usedSize);
        }
}

//向上调整建堆的时间复杂度N*logN
    public void offer(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
        shiftUp(usedSize - 1);
    }
private boolean isFull() {
        return usedSize == elem.length;
    }

2.4 出堆

出堆出的是堆顶元素即下标为0处的元素因为对于数组来说头删是十分不利的因此我们这里学要借助一个小技巧

• 将堆顶元素与堆底元素交换然后将 size - -这样就间接删除了原堆顶元素
• 元素交换后堆的整体有序性将被打破此时需要借助向下调整函数来矫正堆

注意堆的删除一定删除的是堆顶元素。具体如下
1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整
如图所示

刚刚了解了啥叫向上调整那么啥叫向下调整啊

2.4.1 向下调整 

如果父亲节点大于其左右子节点就要将左右子节点中最小的值与父亲节点进行交换直到没有左右子节点或者父节点小于左右子节点。

如图所示

动图演示

向下调整的步骤

---

1. 确认向下调整的父亲这里是删除堆顶元素所以父亲是0
2. 根据公式计算出目标孩子假设左孩子为目标孩子后续会进行判断验证
  左孩子的计算公式 leftChild = parent * 2 + 1
  右孩子的计算公式 rightChild = parent * 2 + 2
  左右孩子间隔为 1判断验证起来也很容易
3. 判断左孩子是否为目标孩子如果不是 child + 1 修改为右孩子是的话就用左孩子
  如果左孩子为最后一个孩子那么此时进行判断验证是非法的因为会涉及到越界问题       因此在判断验证前需要先判断右孩子是否存在即 child + 1 < len
4. 判断当前孩子值与父亲值间的关系假设建大堆如果当前孩子值大于父亲值那么就进行值交换父亲变成孩子重新假设目标孩子如果不满足条件跳出循环即可
5. 循环结束条件为 child < len当 child >= len时说明此时的父亲已经是当前堆中的最小父亲了有孩子的才叫父亲

代码如下

 public void shiftDown(int parent, int len) {
        int child = 2*parent + 1;
        while (child > len) {
            //存在有右孩子的情况
            if (child + 1 > len && elem[child] < elem[child + 1]) {
                child++;
            }
            //找出左右孩子中最大的值与之交换
            if ( elem[child] > elem[parent]) {
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                parent = child;
                child = 2*parent + 1;
            } else {
                break;
            }
        }
    }

📃建堆算法

该部分稍作理解即可

建堆算法是指直接传入一个数组通过这个数组生成对应的大堆小堆建堆的步骤如下

1. 开辟一块足够大的空间作为堆空间
2. 拷贝数组中的所有元素至新空间内
3. 通过两种不同的方式进行堆调整
   • 向上调整效率低
   • 向下调整效率高

两种调整性能比对	时间复杂度	数据量100万	数据量1亿无序	数据量1亿有序
向上调整建堆	F(N) = N*logN	耗时29毫秒	耗时3036毫秒	耗时2310毫秒
向下调整建堆	F(N) = N - log(N + 1)	耗时22毫秒	耗时2372毫秒	耗时1997毫秒

推荐使用向下建堆因为后续的堆排序和Top-K用的都是向下调整

关于堆的其他操作取堆顶元素、当前堆的有效元素数、判断堆是否为空等都是很简单的功能基本逻辑和顺序表一样忘记的可以去看看以前的博客

3. 堆的应用

聊了这么多堆那么我们究竟可以干什么呢

3.1 PriorityQueue的实现

PriorityQueue是用堆作为底层结构封装优先级队列。

我们还有PriorityBlockingQueue。

简单来说PriorityQueue这个Queue继承自AbstractQueue是非线程安全的。

而PriorityBlockingQueue是一个BlockingQueue所以它是线程安全的。

3.2 堆排序

堆排序即利用堆的思想来进行排序总共分为两个步骤

1. 建堆
        升序建大堆
        降序建小堆

2. 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。

具体的堆排序在排序那一章节中会讲到。

更多关于堆的代码我放在了我的gitee上

myHeap/src/TestHeap.java · wjm的码云/java - 码云 - 开源中国 (gitee.com)