“Priority Queue”和“堆排序”有些暧昧！

àì夳堔傛蜴生んèń 2022-10-06 00:33 105阅读 0赞

hello，大家好，我是小慕，今天分享的内容是优先级队列，堆排序的内容。![63d3b8bddcd9b069d3366b9ee20ac6d7.png][]![63d3b8bddcd9b069d3366b9ee20ac6d7.png][]![63d3b8bddcd9b069d3366b9ee20ac6d7.png][]，我们来一起探索研究吧！学知识不能仅仅只学表面，要学就学它的设计原理。

**一、啥是优先级队列(Priority Queue)？**

我们都知道队列是一种特征为FIFO“先进先出”的数据结构，每次从队列中取出的是最早加入队列中的元素。但是，许多应用需要另一种队列，每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列(Priority Queue)，也称为**优先权队列**。

以下图为例，假设胖虎的权重最大，小夫的权重第二，大雄的权重最小。那么入队的时候虽然大雄是最先入队的，小夫第二个入队的，胖虎最后入队。但是出队的时候顺序却不是这样，出队的时候是胖虎第一个出队，然后是小夫，最后才是大雄。  （*这下知道胖虎多难搞了吧，惹不起 ![50b4f6f5909058565bd0936c1a098d02.png][]*）

![0dff05d85c7aa54529f9ef1e99534be6.png][]

而优先级队列的底层原理是怎么样的呢？  其实底层是思想是堆排序。那下面我们就来了解一下堆排序吧！

**二、啥是堆排序？**

**堆的概念： 堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。**

**小根堆（“最小堆”）：**父节点的值比每一个子节点的值都要小，对每一个节点都是如此。

**大根堆（“最大堆”）：**父节点的值比每一个子节点的值都要大，，对每一个节点都是如此。

![7875ffecb843969e95212e8cd83f5885.png][]

**堆排序的存储方式**：在描述堆的操作前，首先来看堆是怎样表示的，一种可能的方法就是使用数组，因为堆在形式上是一颗完全二叉树，用数组来存储它不会浪费任何空间，例如下图就是一个大根堆的存储方案，从根节点开始，从上到下，从左往右依次存储到数组中即可  （**注：数组的0号位置不做存储哦！**）

![09b508d71400d042fef070317bb300d7.png][]

由于堆的形状是一颗完全二叉树，故而我们能发现一些规律

parent(i)= i/2（取整）  （PS：这是求该父节点位置）
    left child(i)=2*i      （PS: 这是求左孩子节点位置）
    right child(i)=2*i +1  （PS: 这是求右孩子节点位置）

**三、堆的shift up**

知道了堆的这些特性以后，我们接下来看看堆的shift up操作吧，shift up操作一般**往堆中添加元素**后需要调整堆的结构而使用的。以下图为例，我们想往一个大根堆中添加一个节点52,首先我们把52放到堆的末尾。

![d8e2b47cbab4c30e686f591f6d2d8a9e.png][]

然后我们发现52的父节点是16，而16比52小，故而我们将两者交换位置，如下图所示

![912cf87a1300428e07a3bad54d57a656.png][]

然后我们发现此时52的父节点是41，而41比52小，故而继续交换52和41的位置，变成如下图

![fbe9635976f27d2d56dc6144f4f82eb8.png][]

这个时候我们再看一下52的父节点是62，而62比52大，故而不需要交换位置，到次，堆的顺序调整就算完成了，这就是所谓的shift up,简单吧

**shift up代码实现：**

private void shiftUp(int k){
       //如果当前节点比父节点大，则和父节点交换位置，直到小于父节点为止    while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
               data.swap(k, parent(k));        k = parent(k);    }}

**四、堆的shift down**

shift down操作一般**往堆中取出一个元素**后需要调整堆的结构而使用的。以下图为例，我们取出该大根堆的第一个元素之后，堆的顶部就是空缺的，如下图所示

![652565529848189ead93d187f61021ba.png][]

这个时候我们就把堆的最后一个元素迁移到这个空位来，如下图，把16这个节点转移堆的顶部

![33109736afac4aafcb1c5c45b6846462.png][]

这个时候我们发现16的两个孩子节点都比它大，先比较子节点 52 和 30 哪个大，和大的交换位置，如下图所示

![ccc12608eb57d966b9c3393503c1e694.png][]

然后此时我们发现16的子节点28和41仍然比它大，于是把16和41交换位置，如下图

![3c39da26ee30d3dfe4f6a41c3770219b.png][]

然后16和它的子节点15进行比较，16大于15，故而不需要交换位置，到此shift down过程就结束了

**shift down完整代码如下**

private void shiftDown(int k){
            //2*k是左孩子的位置        while( 2*k <= count ){
                   int j = 2*k;               //如果右孩子的值大于左孩子的值，则把右孩子的位置赋值给j            if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )                j ++;            // data[j] 是 data[2*k]和data[2*k+1]中的最大值            if( data[k].compareTo(data[j]) >= 0 ) break;            swap(k, j);// 在此轮循环中,data[k]和data[j]交换位置            k = j;        }    }

好啦，今天的内容就到这里了，拜拜，我们下期再见![f67091b5b7f8bf6c94b81cc4ab981f77.png][]

[63d3b8bddcd9b069d3366b9ee20ac6d7.png]: /images/20221005/79a88a8ffe5d4df5916911a6239af8ac.png
[50b4f6f5909058565bd0936c1a098d02.png]: /images/20221005/cbefa62529224a7c883f993fa89a0cfd.png
[0dff05d85c7aa54529f9ef1e99534be6.png]: /images/20221005/34ebad0d45354bb99c35f12d2f57bfa9.png
[7875ffecb843969e95212e8cd83f5885.png]: /images/20221005/8f0a7ea7b14d48e4957d7f53d2f3a843.png
[09b508d71400d042fef070317bb300d7.png]: /images/20221005/5edd48251cbc49f8ae5b7fe785b756ad.png
[d8e2b47cbab4c30e686f591f6d2d8a9e.png]: /images/20221005/6d26cd7ee36242c4a2b660bed72ca788.png
[912cf87a1300428e07a3bad54d57a656.png]: /images/20221005/b04b3a08ee15441491bcd9ed3c62dd43.png
[fbe9635976f27d2d56dc6144f4f82eb8.png]: /images/20221005/f206b257b5614ef0b3c874609eaf7dd7.png
[652565529848189ead93d187f61021ba.png]: /images/20221005/79be30b1d2b64c0bbea3834ded42e68d.png
[33109736afac4aafcb1c5c45b6846462.png]: /images/20221005/cc55d6e2d7ea42cca0d8bc459cdada6b.png
[ccc12608eb57d966b9c3393503c1e694.png]: /images/20221005/944281e9862c4e5cbd88b6c3f340863d.png
[3c39da26ee30d3dfe4f6a41c3770219b.png]: /images/20221005/e24b33fdc33345b9bb704682042946ec.png
[f67091b5b7f8bf6c94b81cc4ab981f77.png]: /images/20221005/798f5a3175f14a68bbe123fadb783520.png