蓝桥杯---优先级队列（关于Topk问题引发的思考）

1.题目概述

1. 这个题目实际上就是和堆相关的一个题目；
2. 堆是被分为大根堆和小跟堆的，我们的这个题目需要的是第K大的元素，这个时候需要使用的元素就是小根堆；
3. 这个Topk创建的是小根堆，而不是大根堆，有些同学觉得，这个最大的第K个元素，我们创建大根堆进行pop不就可以了吗；
4. 实际上这个事极大的增加了我们的空间复杂度的，但是创建小根堆可以解决这个问题：小根堆的话就是父亲是最小的，这个时候父亲向下调整，最后留在我们的堆里面的元素就是前k大的元素，其实两个的差异就是我们的这个方法可以减少空间复杂度的开销；
5. 因为如果是大根堆的话，这个时候不是pop，而是让这个根和我们的叶子结点进行位置的交换，然后去把这个位置进行调整（主要是这个过程浪费空间），然而我们的小根堆就没有这个问题，小根堆就是直接直接往下调整

下面的这个是我当时学习堆的时候写的一个博客，我觉得确实复习起来很方便，大家不理解的话一定要下去看一下，为什么这样去做：

实际上通过这个过程你就可以发现，最后保存在我们的这个堆里面的元素就是topk的元素，正是我们想要的

2.示例说明

下面的这个实例简单的说明一下：

3表示的就是我们要找的就是这个数据里面的第三大的元素；

原本的数据组合就是4,5,8,2，这个时候就是4（第三大）；

接下来就是添加了一个元素3，这个时候在这五个元素里面85432，第三大的就是4

添加5的时候，数组元素就是855432，第三大的就是5；

添加10之后就是10,855432，第三大的就是5；

添加9，之后就是10,9,8,55…这个时候第三大的就是8，以此类推即可；最后这些数据作为结果返回

3.代码分析

1. 这个题目写的其实是构造函数和里面的两个方法，这个和传统的还是有区别的，我觉得；
2. 首先就是创建这个小根堆，和一个数据个数k;
3. 第六航开始的就是这个构造函数，对于这个数组里面的元素进行遍历，添加到我们的堆里面去，如果这个堆里面的元素超过了k值，证明这个堆顶的元素肯定不是第k大的元素；
4. 添加元素的时候也是一个道理，实际上就是把这个元素添加进来，进行判断，大于我们的这个k的时候证明这个堆顶不是第k大的元素，最后直接返回这个堆顶元素即可；
5. 在说明一下：为什么堆顶的就是第K大的元素，我站在自己的理解的角度说明一下：就是我们的这个堆里面最后剩余的就是前k 大的元素，这个又是一个小根堆，因此这个堆顶的元素就是这k个元素里面最小的，也就是第k个元素，对吧；