深入理解 TOP K问题

前面一片文章提过，完全二叉树非常适合用数组这种数据结构来实现。所以堆作为一个完全二叉树肯定用数组来实现最合适。

而且规律也很简单，我们再总结一遍就是：

如果一个节点的下标为i，那么他的左子节点的下标就是2i，右子节点的下标就是2i+1

父节点就是i/2.

还不理解上述 完全二叉树---数组 这种映射关系的 可以看前一篇文章或者自己画一画。

那实现一个堆无非就是要完成对这个堆的 插入数据和删除数据操作。

插入算法

插入操作真的蛮简单的，我们可以看一下刚才那张图，以这个大顶堆为例。 假设我们插入一个值，我们先把这个值 插入在这个 堆的 末尾位置，然后 将这个值 与他的父节点对比，如果比父节点大 那么就交换位置，如果比父节点小 那么就插入完毕。

比方说我们对大顶堆插入一个10的数据，

可以看出来 这个 自下而上 的插入算法还是很好理解的。

删除堆顶元素算法

根据大顶堆和小顶堆的定义可以得知，堆顶元素永远都是最大或者最小的。那么删除堆顶元素以后，新的堆顶元素的值 自然就是 原来堆顶元素的左儿子和右儿子了。

所以显然我们天真的以为删除堆顶元素的算法应该是（假设是大顶堆）：

删除堆顶元素以后，我们将左儿子的值和右儿子的值比较，谁的值比较大，那么就去堆顶呆着。 等儿子去了堆顶位置以后，

儿子的儿子也是一样进行如上操作 看谁大就往上挪一个位置。 看起来这个算法无懈可击也好理解，但是这种算法容易

出现下述异常情况。

所以看的出来这里的算法会导致某种情况下 堆的完全二叉树被破坏掉。

所以我们要将其改进一下，改进后的算法如下：

要删除堆顶元素的时候，先删除堆顶元素然后把堆的最后一个位置的数据放到堆顶，然后自上而下的比对大小，交换位置。

我们来看看，这种算法的图解：

显然这种算法 就会避免第一种算法带来的数组空洞问题。

传说中的堆 排序 就是用这个 堆来实现的吗，具体怎么做的？

是的，堆排序中的堆就是用这个堆来实现数据结构的。实现起来稍微复杂了一丢丢，简单说一下吧（不详细说是因为堆排序实在没啥人用）：

给定一个无序的数组，问，如何用堆这种数据结构来进行排序？

首选把这个无序数组进行建堆的操作，前面说过了插入一个数据的算法，那么对于这个无序数组来说，我们可以假定数组的第一个元素就是堆顶的位置，然后把后面的元素依次按照我们的插入算法 插入即可。（实际上有更加友好的建堆方法，但这不是今天重点，有兴趣的同学可以自己搜索一下）

有了这个堆以后，如何进行排序呢？ 假设是大顶堆，其实对这个堆进行排序就好像我们的删除堆顶元素的算法， 你删了一个堆顶元素以后，第二打的元素不就到对顶了么？以此类推。。。

堆排序为啥没人用呢？

实际上堆排序性能看起来“似乎还可以”，具体时间复杂度和快排序是一样的，时间复杂度都是O(nlogn)，而且还是稳定排序算法。 但是这东西有个致命的缺陷：

堆的操作太多依赖于交换操作，看起来时间复杂度和快排序一样，但是因为你交换次数太多了，所以实际表现远远不如快排序。

就好比举重比赛一样，大家都是一样的成绩，你比我重一点，当然冠军是我。

罗嗦半天堆排序这么垃圾那你还讲他干嘛？

天生我才必有用啊，兄弟，堆这东西 干纯排序不行，其他东西可是有妙用的。

优先级队列 几乎就等于 “堆”

所谓优先级队列就是，不管进入的顺序如何，出去的顺序 是按照优先级来的，仔细想想是不是和我们的大顶堆或者小顶堆的定义 无限趋于一致？熟悉android看过volley源码的同学应该都知道，volley里面的PriorityBlockingQueue 不就是一个线程安全的 用堆这种数据结构来构成的优先级队列么？

再来看经典的TOP K 问题

有了上述基础，我们再来看TOP K问题就简单许多了。leetcode 703 题： leetcode-cn.com/problems/kt…

简单来说，就是给定你一个数组，每次插入数据的时候，要你返回这个数组里面第K大的元素。

下面来说说这道问题的解法思路：

1。 数组中每次插入一个数据的时候，我们都进行快排序，然后取出第k个大小就可以。这是思路上最简单但是最蠢的方法。 因为每次插入一个数据都要全部排序 那也太慢了。

2. 在知道有优先级队列这么个东西以后，我们就可以维持一个 k大小的 小顶堆，每次有新元素进来的时候 我们就看看这个新元素 的值 是不是比这个小顶堆的值要大，如果比他大 那么就把这个小顶堆的堆顶元素删掉，然后插入我们这个新元素的值以后， 再取这个小顶堆的堆顶元素 就是我们的第k大元素了。

class KthLargest {

   
    PriorityQueue<Integer> queue;
    
    int maxHeapSize;

    public KthLargest(int k, int[] nums) {
        //初始化一个大小为k的小顶堆
        queue = new PriorityQueue<Integer>(k);
        maxHeapSize=k;

        if (k < nums.length) {
            //先构造一个大小为k的 堆
            for (int i = 0; i < k; i++) {
                queue.add(nums[i]);
            }
            //下面构造的时候要判断大小
            for (int j = k; j < nums.length; j++) {
                if (nums[j] > queue.peek()) {
                    queue.poll();
                    queue.offer(nums[j]);
                } else {

                }
            }

        } else {
            for (Integer integer : nums) {
                queue.add(integer);
            }
        }
    }

    public int add(int val) {
        
        if(queue.size()<maxHeapSize)
        {
            queue.offer(val);
            return queue.peek();
        }
        
        if (val > queue.peek()) {
            queue.poll();
            queue.offer(val);
        }
        return queue.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */
复制代码

看下效果：

嗯 还可以。

然后最后看下leetcode 239问题 leetcode-cn.com/problems/sl…

有了优先级队列以后这个问题也变的简单了吧。只要遍历数组的时候维护一个大顶堆，问题就迎刃而解了。（代码就不上了，很简单）

当然其实这个问题还有更好的解法，就是不用堆，而用双端队列，有兴趣的同学可以研究下。

堆或者说优先级队列还能解决什么实际生产问题吗？

其实能解决的生产问题很多，比方说，我们做Android定制系统的，假设用户搞了N个任务在那里，每个任务都有特定的执行时间， 到了时间就要执行用户的任务，比如说闹钟。那我们怎么完成这个需求呢？

每过一秒就检查 任务列表 有没有时间跟当前时间符合的吗？显然不行，这样效率太低。

我们可以把这些任务存储成为一个小顶堆，这样只要系统时间过一秒，我们就看看是不是和堆顶元素时间一样即可。