专栏首页陌无崖知识分享go实现利用最大堆寻找最小k个数

go实现利用最大堆寻找最小k个数

作者 | 陌无崖

转载请联系授权

导语

昨天分享了寻找最小k个数的算法是,那么有没有更为迅速的方法呢?今天就来分享关于如何使用最大堆进行解决。

什么是堆

我太懒了,直接上我画好的思维导图吧哈哈,获取高清的也可以关注我的公众号,后台回复【堆】

思路设计

知道了如上定义,我们就可以将容量为K的最大堆存储我们的最小k个数,因此我们仍然可以按照之前的方法假设堆中存储的仍然是最小的k个数(不懂的可以看我的上一篇文章),再通过比较替换或不替换堆来最终找到我们的最小的k个数。此解法与解法二类似但由于使用堆时进行查找或更新的时间复杂度降低到了O(logk),那么通过遍历剩余的n-k个数,那么最坏情况下的时间复杂度为O(k + (n-k)logk) = O(nlogk)。这里的O(k)为建堆时的时间复杂度。

因此我们需要建堆,通过以上的分析我们可以用一维数组存储我们的堆,我们先来看一个完全二叉树找一下规律

我们将1,2,3,4,5分别作为下标,在上个图片的思路中,我们可以发现每次我们的遍历刚开始指向的是一个由子节点的父节点,在下图中可知子节点(i)和父节点(l)之间的关系是2 * i + 1 = l,且在同一深度相邻节点相差为1,由上图可知,我们在遍历父节点比较时,依次会经过5,4,3,2,1,0这些下标指向的数值。因此我们可以依次为循环,每次循环的操作都是父节点和子节点进行比较。

代码分析

(1) 循环每一个父节点

(2) 在子节点中找到最大值和父节点比较,若子节点大,则替换

(3) 每次提换后需要记录新的父节点,重新和子节点比较,替换,如下标为2和5的进行替换后,还要保证下标5(原来的下标2)是否满足最大堆性质。因为是同样的操作,因此该过程仍然是一个循环,循环结束的标志是最后一层的叶节点。

完整代码

func BuildMaxHeap(data []int) {
  for i := len(data)/2 - 1; i >= 0; i-- {
    adjustDown(data, i)
  }
}
func adjustDown(data []int, i int) {

  for largest := 2*i + 1; largest < len(data); largest = 2*largest + 1 {
    if largest == len(data)-1 {
      if data[largest] > data[i] {
        // fmt.Println(data[largest], "和", data[i], "进行交换")
        data[largest], data[i] = data[i], data[largest]
        i = largest
      } else {
        // fmt.Println(data[largest], "不和", data[i], "进行交换")
      }
    } else {
      if data[largest+1] > data[largest] && data[largest+1] > data[i] {
        // fmt.Println(data[largest+1], "和", data[i], "进行交换")
        data[largest+1], data[i] = data[i], data[largest+1]
        i = largest
      } else if data[largest+1] < data[largest] && data[largest] > data[i] {
        // fmt.Println(data[largest], "和", data[i], "进行交换")
        data[largest], data[i] = data[i], data[largest]
        i = largest
      } else {
        // fmt.Println(data[largest], "或", data[largest+1], "不和", data[i], "进行交换")
      }
    }
  }
}

// 维护最大堆
func topK(data []int, k int) {
  // 建立前K个数的最大堆
  BuildMaxHeap(data[0:k])
  for i := k; i < len(data); i++ {
    if data[i] < data[0] { //如果剩余的数中有小的数则替换
      data[i], data[0] = data[0], data[i]
      adjustDown(data[0:k], 0)
    }
  }
}

本文分享自微信公众号 - golang技术杂文(gh_ebbdb61f463e),作者:无崖子天下无敌

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【go】剑指offer:常见排序算法

    冒泡排序是比较简单的排序算法,它的关键思想是移动指针不断的进行两两比较,将最大的数字不断的进行更换位置,直至到最后,即完成一趟比较,都会寻找到最大的数字,且最大...

    陌无崖
  • 寻找和为定值的两个数

    输入一个整数数组和一个整数,在数组中查找一对数,满足他们的和正好是输入的那个整数,如果有多对数的和等于输入的整数,则全部输出,要求输出的结果中不应该出现重复,如...

    陌无崖
  • 【go】剑指offer:不同程序员遇到相同的题

    该题可以说是初级程序员的水平,然而却有很多程序员的解决思路并不是完美。现在一起看看不同程序员的解决思路吧~

    陌无崖
  • 使用脚手架应用做单元测试

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    Jerry Wang
  • [半zz]迅雷笔试题

    用户1130771
  • 从0到1掌握R语言网络爬虫

    引言 网上的数据和信息无穷无尽,如今人人都用百度谷歌来作为获取知识,了解新鲜事物的首要信息源。所有的这些网上的信息都是直接可得的,而为了满足日益增长的数据需求,...

    小莹莹
  • 通过空气质量指数AQI学习统计分析并进行预测(上)

    AQI(空气质量指数),用来衡量空气清洁或者污染的程度。值越小,表示空气质量越好。近年来,因为环境问题,空气质量也越来越受到人们的重视。

    朱小五
  • 使用 Python 实现几种常见的排序算法

    冒泡排序是最为基础的排序算法,其核心思想就是相邻元素两两比较,把较大的元素放到后面,在一轮比较完成之后,最大的元素就位于最后一个位置了,就好像是气泡,慢慢的浮出...

    周萝卜
  • 讲讲切比雪夫定理

    前面讲了大数定理,讲了中心极限定理,有读者留言让讲讲切比雪夫定理,安排。这一篇就来讲讲切比雪夫定理。

    张俊红
  • C++ string实现

    作为C++从业者,我相信都会被考察过实现简单的string类,包括构造、析构、拷贝构造以及赋值拷贝等,因为这能够很好的考察面试者的C++基本功。借看《剑指off...

    evenleo

扫码关注云+社区

领取腾讯云代金券