本篇内容介绍了“Java怎么用堆解决Top-k问题”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！堆其实就是一种二叉树，但是普通的二叉树是以链式结构进行储存数据的，而堆是以数组进行顺序存储数据的。那么什么样的二叉树才适合用顺序存储的方式呢？我们假设一颗普通的二叉树可以用数组存储，那么就可以得到如下结构：我们可以看到，当二叉树中间有空值时，数组的存储空间会被浪费，那么什么情况下空间才不免费云主机域名会被浪费呢？ 那就是完全二叉树。从以上结构中，我们不能用链式结构的指针来访问孩子节点或者父亲节点，只能通过对应下标来访问，其实也比较简单。例如下图：已知 2 节点的下标是1，那么他的左孩子下标是：2 * 2 + 1 = 3他的右孩子下标是：2 * 2 + 2 = 4相反，已知 1 节点的下标是3，3 节点的下标是4，那么1 节点的父亲节点下标是：(3 – 1) / 2 = 13 节点的父亲节点下标是：(4 – 1) / 2 = 1大根堆保证，每颗二叉树的根节点都 大于 左右孩子节点从最后一棵子树的根节点开始调整，来到每颗子树的根节点，使得每棵子树都向下调整为大根堆，最后再向下做最后调整，保证二叉树整体是大根堆（这个调整主要是为了后面的堆排序）。具体调整过程如下：怎么用代码实现呢？我们首先从最后一棵子树调整，那么就要拿到最后一颗子树的根节点 parent ，我们知道数组最后一个节点下标是 len – 1，而这个节点是最后一棵子树的左孩子或者右孩子，根据孩子下标就可以拿到根节点下标( parent ) ，parent– 就可以让每颗子树都进行调整，直到来到根节点，再向下调整最后一次，便可以得到大根堆。小根堆保证，每颗二叉树的根节点都 小于 左右孩子节点调整过程同上。在java中，提供了堆这种数据结构（PriorityQueue），也叫优先级队列，当我们创建一个这样的对象时，就得到了一个没有添加数据的 小根堆 ，我们可以向里面添加或者删除元素，每向里面删除或者添加一个元素，系统会整体进行一次调整，重新又调整为小根堆。例：有一堆元素，让你找出前三个最小的元素。思路一： 将数组从小到大排序，拿到数组前3个元素。但是可以发现这样时间复杂度太高，不可取。思路二： 将元素全部放入一个堆结构中，然后弹出三个元素，每次弹出的元素都是当前堆最小的，那么弹出的三个元素就是前最小的三个元素。这种思路可以做，但是假设我有1000000个元素，只弹出前三个最小的元素，那么就要用到大小为1000000的堆。这么做空间复杂度太高，不建议用这种方法。思路三：我们需要得到三个最小的元素，那么就建一个大小为3的堆，假设目前的堆结构中刚好放满了3个元素，那么这三个元素就是当前最小的三个元素。假设第四个元素是我们想要的元素之一，那么前三个至少有一个元素不是我们想要的，就需要弹出，那么弹出谁呢？我们要得到的是前三个最小的元素，所以当前堆结构中最大的元素一定不是我们想要的，所以这里我们建一个大根堆。弹出该元素，然后放入第四个元素，直到遍历完整个数组。这样我们就得到了只含有前三个最小元素的堆，并且可以看到堆的大小一直都是3，而不是有多少数据就建多大的堆，然后再依次弹出元素就行了。“Java怎么用堆解决Top-k问题”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注百云主机网站，小编将为大家输出更多高质量的实用文章！
这篇文章主要介绍“C++如何实现xml解析器”，在日常操作中，相信很多人在C++如何实现xml解析器问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++如何实现xml解析器”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！我们来…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
