topk堆java的简单介绍
今天给各位分享topk堆java的知识，其中也会对进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
【排序】堆、完全二叉树、堆排序、PriorityQueue、TopK
可以利用堆、外排序的方法来做多个处理单元的结果合并
堆，其实就是一个完全二叉树；
完全二叉树，要么是一个满二叉树，要么叶子节点层为从左到右；
堆，实际中是可以用数组实现的；
规律，把数组脑补成完全二叉树
节点 n 的左孩子为 2*n + 1 ,也就是 n1 +1
节点 n 的左孩子为 2*n + 2 ,也就是 n1 +2
节点 n 的父节点为 (n-1)/2 ,也就是 (n-1)2
堆分为小根堆、大根堆
小根堆：在完全二叉树中， 任何一个子树 的最小值都在头部，小根堆，数组最小值在 arr[0]
大根堆：在完全二叉树中， 任何一个子树 的最大值都在头部，大根堆，数组最大值在 arr[0]
思想：1、根据大根堆的特点，先将一个数组构建成为一个大根堆，这样堆顶就是最大的
2、再将堆顶和最后一个数互换，将最大的数放到最后，随即调整维持大根堆
继续互换、调整。
java实现的堆结构、优先级队列， PriorityQueue()
PriorityQueue当size达到了初始的initialCapacity容量后会进行扩容，每次容量加1。
1-1
1,2-1.5
1,2,3-2
...
准备一个大根堆，一个小根堆
把小于等于大根堆对顶的树插入大根堆，
把大于大根堆对顶的树插入小根堆；
同时，要调整大根堆和小根堆的数量，数量差值不要超过1；
如果大根堆的size大了，就把大根堆 的堆顶取出插入小根堆；
如果小根堆的size大了，就把小根堆 的堆顶取出插入大根堆；
这样就能达到，大根堆，小根堆数量保持平衡，同时大根堆中的小的n/2个数，小根堆中是大的n/2个数，
（大根堆堆顶+小根堆堆顶）/2 就是流的中位数
假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。
思路： 利用一个小根堆，把每个文件的第一条记录取出来，放入小根堆中，那么小根堆的堆顶就是这100条记录中顺序最小的记，它为记录A，也是这100个文件中顺序最小的，将这个堆顶追加到准备的大文件。从记录A原来所在的文件中再取出一条记录，放入小根堆，取出堆顶，如此重复...
思路： 利用一个size为k的堆，求最大的Top K 用小根堆 ，求最小的Top k用大根堆。
我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。
遍历数组需要 O(n) 的时间复杂度，一次堆化操作需要 O(logK) 的时间复杂度，所以最坏情况下，n 个元素都入堆一次，所以时间复杂度就是 O(nlogK)。
使用mapkey,count计数，count放入小根堆中，多个小根堆合并求top10.
分析：假设一条搜索50个字节，10亿条那么就占用了50GB的大小，所以一次对所有数据进行统计是不可行的。
0、准备10个空文件
1、采用hash 算法将日志进行计算之后得到hash值，模10，存放入对应的文件中。那么每个文件大概会有1亿条记录，假设平均每条关键词重复10次，那么就是1000万条关键词，大概500MB，1G的内存是可以存下的
2、使用hashmap对每个小文件中的关键词进行数量统计，对每个小文件的统计的结果存入一个Size为10 的小根堆。
3、对这10个小根堆再进行合并得到最终的Top 10 的搜索关键词
推荐阅读：
数据结构和算法|堆的应用
Java 实习生应具备哪些知识、能力？
01、Java基础
认真看一遍 Java核心技术卷一，会常见的集合类用法，最主要两个 ArrayList 和 HashMap，水平到可以刷 leetcode easy 和一些集合类操作的 medium 就OK。其中更进一步可以看看 ArrayList 的源码（这部分源码几乎没有什么难点），有助于理解接口和抽象类的使用。
另外，针对目前主要的Java面试，我觉得Java内存模型、GC、线程安全、线程池这些需要了解，不管面试会不会问，至少应该要知道Java有这些东西，可以通过看深入理解Java虚拟机和Java并发编程实战补充这部分知识，实习工作应该不会接触到这些，但还是那句话，这些概念要知道。
02、熟悉一个数据库和基本SQL语句
数据库主流就是MySQL了，熟悉MySQL的安装、启动、可视化工具（workbench、navicat等），知道什么是隔离级别，SQL语句会写基本的select，insert，update和两张表的 inner join，外加增加字段、修改字段的ddl语句，理解索引原理和innodb特点。这里有条件的可以用学生价买一个云主机，国内阿里云腾讯云都行，熟悉在 CentOS 或者是 Ubuntu 里命令行安装和使用MySQL。
另外，作为拓展，可以去了解一下redis的基本使用，作为现在大热的组件，其实却非常容易上手，一些技术面试很喜欢问。
03、了解一个Java Web框架
推荐 Spring+SpringMVC+Mybatis（我不太推荐一上来就学 Sping Boot），先自己本地搭建一个这样的环境。
有个很好的学习地方就是github，例如：手把手教你整合最优雅SSM框架，跟着这种教程一步一步耐心的配置一个web开发环境。对于Spring重点理解 IOC和AOP。
推荐使用 Intellij IDEA 进行编码，学会 Git 的使用，命令包括切换分支、创建分支，add、commit、push、merge(理解什么叫conflict和怎么修复)，不论是用命令行还是IDEA提供的图形界面都可以，我强烈推荐后者，因为用过你就知道它有多好用。
04、了解一点前端知识
这里以我的经验来讲，你需要会简单 html、css、js（angularjs 1.x）和 jQuery，其中前两者你还需要知道一个 bootstrap，根据文档能用它的组件实现你需要的效果，你学习这些东西要多久呢？可能三天吧。。。只需要知道其中最基本的写法，能实现项目中的需求，如果之后工作遇到不会的随时可以百度学习，所以我觉得这不算很艰巨的任务。
05、基于SSM框架实现一个项目
用烂的就是网上书店、个人博客这类，虽然老掉牙，但是对熟悉数据库操作、训练增删改查的业务逻辑编写却屡试不爽，其中你需要注意的一些点：
代码风格，包括驼峰命名法、数据库字段、类型、表名等的设置，注意面向接口而不要面向实现编程。
MVC 究竟在干吗，我dao、service里写的代码怎么差不多啊，那为什么要做两层？controller里需要做些什么？
再深入（对于题主需求可能可以忽略但需要了解），登录时的密码存储怎么做？明文么？session管理怎么搞？事务配置怎么设置？我怎么url一变直接跳进后台了，这部分怎么做权限控制？前端分页、后端分页都是怎么弄的等等
最后，将你的应用发布到你买的云主机上试试，熟悉基本的 cd、tar、scp、vi、vim、tomcat配置运行等基本命令，有助于之后的实习工作
06、刷一些简单的手写算法题
这些程序员面试中几乎不可避免，高频的题目无非就是快排、二分查找、topK、二叉树三种遍历、两个栈模拟队列等等。
07、写在最后
做完上述我觉得应聘一个不说大公司吧，普通公司的Java实习生就已经ok了，唯一不足是鉴于你的学历如果想进大公司只能做到比我说的要更优秀，但是技术不是过分在意出身，可以说努力就有机会。
最后，面试前还是要多看看各种面经，好好准备一下常问的题目，写一份简单的、清爽的简历。
Java软件工程师主要学习哪些课程？
01、Java基础
认真看一遍 Java核心技术卷一，会常见的集合类用法，最主要两个 ArrayList 和 HashMap，水平到可以刷 leetcode easy 和一些集合类操作的 medium 就OK。其中更进一步可以看看 ArrayList 的源码（这部分源码几乎没有什么难点），有助于理解接口和抽象类的使用。
另外，针对目前主要的Java面试，我觉得Java内存模型、GC、线程安全、线程池这些需要了解，不管面试会不会问，至少应该要知道Java有这些东西，可以通过看深入理解Java虚拟机和Java并发编程实战补充这部分知识，实习工作应该不会接触到这些，但还是那句话，这些概念要知道。
02、熟悉一个数据库和基本SQL语句
数据库主流就是MySQL了，熟悉MySQL的安装、启动、可视化工具（workbench、navicat等），知道什么是隔离级别，SQL语句会写基本的select，insert，update和两张表的 inner join，外加增加字段、修改字段的ddl语句，理解索引原理和innodb特点。这里有条件的可以用学生价买一个云主机，国内阿里云腾讯云都行，熟悉在 CentOS 或者是 Ubuntu 里命令行安装和使用MySQL。
另外，作为拓展，可以去了解一下redis的基本使用，作为现在大热的组件，其实却非常容易上手，一些技术面试很喜欢问。
03、了解一个Java Web框架
推荐 Spring+SpringMVC+Mybatis（我不太推荐一上来就学 Sping Boot），先自己本地搭建一个这样的环境。
有个很好的学习地方就是github，例如：手把手教你整合最优雅SSM框架，跟着这种教程一步一步耐心的配置一个web开发环境。对于Spring重点理解 IOC和AOP。
推荐使用 Intellij IDEA 进行编码，学会 Git 的使用，命令包括切换分支、创建分支，add、commit、push、merge(理解什么叫conflict和怎么修复)，不论是用命令行还是IDEA提供的图形界面都可以，我强烈推荐后者，因为用过你就知道它有多好用。
04、了解一点前端知识
这里以我的经验来讲，你需要会简单 html、css、js（angularjs 1.x）和 jQuery，其中前两者你还需要知道一个 bootstrap，根据文档能用它的组件实现你需要的效果，你学习这些东西要多久呢？可能三天吧。。。只需要知道其中最基本的写法，能实现项目中的需求，如果之后工作遇到不会的随时可以百度学习，所以我觉得这不算很艰巨的任务。
05、基于SSM框架实现一个项目
用烂的就是网上书店、个人博客这类，虽然老掉牙，但是对熟悉数据库操作、训练增删改查的业务逻辑编写却屡试不爽，其中你需要注意的一些点：
代码风格，包括驼峰命名法、数据库字段、类型、表名等的设置，注意面向接口而不要面向实现编程。
MVC 究竟在干吗，我dao、service里写的代码怎么差不多啊，那为什么要做两层？controller里需要做些什么？
再深入（对于题主需求可能可以忽略但需要了解），登录时的密码存储怎么做？明文么？session管理怎么搞？事务配置怎么设置？我怎么url一变直接跳进后台了，这部分怎么做权限控制？前端分页、后端分页都是怎么弄的等等
最后，将你的应用发布到你买的云主机上试试，熟悉基本的 cd、tar、scp、vi、vim、tomcat配置运行等基本命令，有助于之后的实习工作
06、刷一些简单的手写算法题
这些程序员面试中几乎不可避免，高频的题目无非就是快排、二分查找、topK、二叉树三种遍历、两个栈模拟队列等等。
topK的3种解法
思路：
（1）可以避免对所有数据进行排序，只排序部分；
（2） 冒泡排序是每一轮排序都会获得一个最大值，则K轮排序即可获得TopK。
时间复杂度空间复杂度：（1）时间复杂度：排序一轮是O(N)，则K次排序总时间复杂度为：O(KN)。（2）空间复杂度：O(K)，用来存放获得的topK，也可以O(1)遍历原数组的最后K个元素即可。
思路：
（1）堆：分为大顶堆（堆顶元素大于其他所有元素）和小顶堆（堆顶其他元素小于所有其他元素）。
（2）我们使用小顶堆来实现。
（3） 取出K个元素放在另外的数组中，对这K个元素进行建堆。
（4） 然后循环从K下标位置遍历数据，只要元素大于堆顶，我们就将堆顶赋值为该元素，然后重新调整为小顶堆。
（5） 循环完毕后，K个元素的堆数组就是我们所需要的TopK。
时间复杂度与空间复杂度：
（1）时间复杂度：每次对K个元素进行建堆，时间复杂度为：O(KlogK)，加上N-K次的循环，则总时间复杂度为O((K+(N-K))logK)，即O(NlogK)，其中K为想要获取的TopK的数量N为总数据量。
（2）空间复杂度：O(K)，只需要新建一个K大小的数组用来存储topK即可
思路：
（1）比如有10亿的数据，找处Top1000 ，我们先将10亿的数据分成1000份，每份100万条数据。
（2） 在每一份中找出对应的Top 1000，整合到一个数组中，得到100万条数据，这样过滤掉了999%%的数据。
（3） 使用快速排序对这100万条数据进行”一轮“排序，一轮排序之后指针的位置指向的数字假设为S，会将数组分为两部分，一部分大于S记作Si，一部分小于S记作Sj。
（4） 如果Si元素个数大于1000，我们对Si数组再进行一轮排序，再次将Si分成了Si和Sj。如果Si的元素小于1000，则我们需要在Sj中获取1000-count(Si)个元素的，也就是对Sj进行排序（5）如此递归下去即可获得TopK。
时间复杂度与空间复杂度：
（1）时间复杂度：一份获取前TopK的时间复杂度：O((N/n)logK)。则所有份数为：O(NlogK)，但是分治法我们会使用多核多机的资源，比如我们有S个线程同时处理。则时间复杂度为：O((N/S)logK)。之后进行快排序，一次的时间复杂度为：O(N),假设排序了M次之后得到结果，则时间复杂度为：O(MN)。所以 ，总时间复杂度大约为O(MN+(N/S)logK) 。
（2）空间复杂度：需要每一份一个数组，则空间复杂度为O(N)。
关于topk堆java和的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
发布于：2022-12-10，除非注明，否则均为原创文章，转载请注明出处。