【数据结构】优先级队列(堆)与堆的建立

古城微笑少年丶 2024-04-17 10:34 36阅读 0赞

#### 文章目录 ####

*  ?优先级队列
 *   *  ??优先级队列的概念
 *  ?堆的由来
 *   *  ??堆的概念
     *  ??堆的性质
     *  ??堆的存储方式
 *  ?堆的创建
 *   *  ??堆向下调整
     *  ??代码实现
     *   *  ?代码测试结果展示
 *  ?建堆的时间复杂度
 *  ⭕总结

## ?优先级队列 ##

![在这里插入图片描述][0df8e840d4dc42d080ee14b3e309d167.png]

### ??优先级队列的概念 ###

前面介绍过队列，***队列是一种先进先出(FIFO)的数据结构***，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适。

比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。

在这种情况下，***数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象***。这种数据结构就是优先级队列(Priority Queue)。

## ?堆的由来 ##

为了模拟实现优先级队列的模拟实现，JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。

### ??堆的概念 ###

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

### ??堆的性质 ###

*  堆中某个节点的值总是不大于或不小于其父节点的值；
 *  堆总是一棵完全二叉树。

![在这里插入图片描述][42b6be37bef84852a4491cddb81e5d74.png]

### ??堆的存储方式 ###

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

![在这里插入图片描述][fe54a61738c044cea75a3e29500ccd1d.png]  
***注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低***

将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：

*  如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
 *  如果2 \* i + 1 小于节点个数，则节点i的左孩子下标为2 \* i + 1，否则没有左孩子
 *  如果2 \* i + 2 小于节点个数，则节点i的右孩子下标为2 \* i + 2，否则没有右孩子

## ?堆的创建 ##

### ??堆向下调整 ###

对于集合\{ 27,15,19,18,28,34,65,49,25,37 \}中的数据，如果将其创建成堆呢？  
![在这里插入图片描述][fbedadf07737427b8e25e0e6351729ef.png]

仔细观察上图后发现：***根节点的左右子树已经完全满足堆的性质，因此只需将根节点向下调整好即可。***

向下过程(以小堆为例)：

1.  让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)
2.  如果parent的左孩子存在，即:child < size， 进行以下操作，直到parent的左孩子不存在

> parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标  
> 将parent与较小的孩子child比较，如果
> 
>  *  parent小于较小的孩子child，调整结束
>  *  否则：交换parent与较小的孩子child，交换完成之后，parent中大的元素向下移动，可能导致子树不满足对的性质，因此需要继续向下调整  
>     即parent = child；child = parent\*2+1; 然后继续2。

![在这里插入图片描述][ef561736e8824b8290b84c25819dad1e.png]  
大堆实现与其类似

### ??代码实现 ###

public class MyHeap {
        
        public void shiftDown(int[] array, int parent) {
        
            // child先标记parent的左孩子，因为parent可能右左没有右
            int child = 2*parent + 1;
            int size = array.length;
            while(child < size ) {
        
                // 如果右孩子存在，找到左右孩子中较小的孩子,用child进行标记
                if(child + 1 < size) {
        
                    if(array[child + 1] < array[child]) {
        
                        child = child + 1;
                    }
                }
                // 如果最小的孩子比其父亲还小，说明该结构没有满足堆的特性，进行交换
                if(array[child] < array[parent]) {
        
                    int tmp = array[parent];
                    array[parent] = array[child];
                    array[child] = tmp;
                } else {
        
                    //满足就退出循环
                    break;
                }
                // parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
                parent = child;
                child = 2*parent + 1;
            }
        }
    }

#### ?代码测试结果展示 ####

测试代码

public class TestMain {
        
        public static void main(String[] args) {
        
            MyHeap myHeap = new MyHeap();
            int[] array = {
        27,15,19,18,28,34,65,49,25,37};
            System.out.println("调整前：");
            for(int i = 0; i < array.length ; i++) {
        
                System.out.print(array[i] + " ");
            }
            for(int parent = (array.length-2)/2 ; parent >= 0; parent --) {
        
                myHeap.shiftDown(array, parent);
            }
            System.out.println();
            System.out.println("调整后：");
            for(int i = 0; i < array.length ; i++) {
        
                System.out.print(array[i] + " ");
            }
            System.out.println();
        }
    }

测试结果  
![在这里插入图片描述][11d8bdf8d43944c8923aa0c7f696de45.png]

***注意：在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。***

时间复杂度分析：

最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为  
![在这里插入图片描述][ccc0fb1bdf5d4e4f9e0ff3f670698611.png]

## ?建堆的时间复杂度 ##

对于普通的序列\{ 1,5,3,8,7,6 \}，我们需要建立大堆，即根节点的左右子树不满足堆的特性，又该如何调整呢？  
![在这里插入图片描述][80aebef6c2424340a76501a0b6a6e394.png]  
做法如下：

找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整

for(int parent = (array.length-2)/2 ; parent >= 0; parent --) {
        
    	myHeap.bigDown(array, parent);
    }

那么时间复杂度又为多少呢？

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

![在这里插入图片描述][a7f4e3a644d142bcba4d85cc935d3f03.png]  
因此：建堆的时间复杂度为O(N)

## ⭕总结 ##

关于《【数据结构】 优先级队列(堆)与堆的建立》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！

[0df8e840d4dc42d080ee14b3e309d167.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/c678a90178bd43bcb5a1bb1ed5e6a288.png
[42b6be37bef84852a4491cddb81e5d74.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/3a6090548de541ad9eb3bfa8cc23ee34.png
[fe54a61738c044cea75a3e29500ccd1d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/50c973be61c84c3d9fa49378bb905b8d.png
[fbedadf07737427b8e25e0e6351729ef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/af32d2810dc74b579aab3b7e08e8478a.png
[ef561736e8824b8290b84c25819dad1e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/cb771becd1a94a999f548f79d94714f3.png
[11d8bdf8d43944c8923aa0c7f696de45.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/67c3b700ba3347478815b43d658f609c.png
[ccc0fb1bdf5d4e4f9e0ff3f670698611.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/6b160957dc974575923b6cc83aea81a5.png
[80aebef6c2424340a76501a0b6a6e394.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/b5f02714c2c5489e92a812fa9c6b2273.png
[a7f4e3a644d142bcba4d85cc935d3f03.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/620d26fc289c48b6bfec4d2885c5016a.png