深入理解 TOP K问题

综合技术 2018-12-09 阅读原文

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

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

如果一个节点的下标为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个大小就可以。这是思路上最简单但是最蠢的方法。 因为每次插入一个数据都要全部排序 那也太慢了。

  1. 在知道有优先级队列这么个东西以后,我们就可以维持一个 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个任务在那里,每个任务都有特定的执行时间, 到了时间就要执行用户的任务,比如说闹钟。那我们怎么完成这个需求呢?

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

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

稀土掘金

责编内容by:稀土掘金阅读原文】。感谢您的支持!

您可能感兴趣的

浅解前端必须掌握的算法(五):堆排序(上)... 虽然前端面试中很少会考到算法类的题目,但是你去比如像腾讯一样的大厂面试的时候就知道了,对基本算法的掌握对于从事计算机科学技术的我们来说,还是必不可少的,每天花上 10 分钟,轻松了解基本算法概念以及前端的实现方式。 另外,掌握了一...
【算法与数据结构专场】堆排序是什么鬼?... 排序算法相必大家都见过很多种,例如快速排序、归并排序、冒泡排序等等。今天,我们就来 简单 讲讲 堆排序 。 在上一篇中,我们讲解了 二叉堆 ,今天的堆排序算法主要就是依赖于 二叉堆 来完成的,不清楚二叉堆是什么鬼的,可以看下: ...
堆排序 堆(heap),这里所说的堆是数据结构中的堆,而不是内存模型中的堆。堆通常是一个可以被看做一棵树,它满足下列性质: 堆中任意节点的值总是不大于(不小于)其子节点的值; 堆总是一棵 完...
浅解前端必须掌握的算法(五):堆排序(下)... 虽然前端面试中很少会考到算法类的题目,但是你去比如像腾讯一样的大厂面试的时候就知道了,对基本算法的掌握对于从事计算机科学技术的我们来说,还是必不可少的,每天花上 10 分钟,轻松了解基本算法概念以及前端的实现方式。 另外,掌握了一些基本...
C++: 直接插入排序,冒泡排序,快速排序,堆排序和归并排序... 看了总结图,我这里就总结一下 直接插入排序,冒泡排序,快速排序,堆排序和归并排序,使用C++实现 重新画了总结图 直接插入排序 整个序列分为有序区和无序区,取第一个元素作为初始有序区,然后第二个开始,依次插入到...