Java中如何使用堆来解决Top |
您所在的位置:网站首页 › 在eclipse中如何调节字体大小 › Java中如何使用堆来解决Top |
1、什么是堆?堆结构 堆其实就是一种二叉树,但是普通的二叉树是以链式结构进行储存数据的,而堆是以数组进行顺序存储数据的。那么什么样的二叉树才适合用顺序存储的方式呢? 我们假设一颗普通的二叉树可以用数组存储,那么就可以得到如下结构: 我们可以看到,当二叉树中间有空值时,数组的存储空间会被浪费,那么什么情况下空间才不会被浪费呢? 那就是完全二叉树。 从以上结构中,我们不能用链式结构的指针来访问孩子节点或者父亲节点,只能通过对应下标来访问,其实也比较简单。 例如下图: 已知 2 节点的下标是1,那么 他的左孩子下标是:2 * 2 + 1 = 3 他的右孩子下标是:2 * 2 + 2 = 4 相反,已知 1 节点的下标是3,3 节点的下标是4,那么 1 节点的父亲节点下标是:(3 - 1) / 2 = 1 3 节点的父亲节点下标是:(4 - 1) / 2 = 1 大根堆保证,每颗二叉树的根节点都 大于 左右孩子节点 从最后一棵子树的根节点开始调整,来到每颗子树的根节点,使得每棵子树都向下调整为大根堆,最后再向下做最后调整,保证二叉树整体是大根堆(这个调整主要是为了后面的堆排序)。 具体调整过程如下: 怎么用代码实现呢? 我们首先从最后一棵子树调整,那么就要拿到最后一颗子树的根节点 parent ,我们知道数组最后一个节点下标是 len - 1,而这个节点是最后一棵子树的左孩子或者右孩子,根据孩子下标就可以拿到根节点下标( parent ) ,parent-- 就可以让每颗子树都进行调整,直到来到根节点,再向下调整最后一次,便可以得到大根堆。 小根堆保证,每颗二叉树的根节点都 小于 左右孩子节点 调整过程同上。 在java中,提供了堆这种数据结构(PriorityQueue),也叫优先级队列,当我们创建一个这样的对象时,就得到了一个没有添加数据的 小根堆 ,我们可以向里面添加或者删除元素,每向里面删除或者添加一个元素,系统会整体进行一次调整,重新又调整为小根堆。 // 默认得到一个小根堆 PriorityQueue smallHeap = new PriorityQueue(); smallHeap.offer(23); smallHeap.offer(2); smallHeap.offer(11); System.out.println(smallHeap.poll());// 弹出2,剩余最小的元素就是11,会被调整到堆顶,下一次弹出 System.out.println(smallHeap.poll());// 弹出11 // 如果需要得到大根堆,在里面传一个比较器 PriorityQueue BigHeap = new PriorityQueue(new Comparator() { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } });登录后复制2、top-k问题解决思路例:有一堆元素,让你找出前三个最小的元素。 思路一: 将数组从小到大排序,拿到数组前3个元素。但是可以发现这样时间复杂度太高,不可取。 思路二: 将元素全部放入一个堆结构中,然后弹出三个元素,每次弹出的元素都是当前堆最小的,那么弹出的三个元素就是前最小的三个元素。 这种思路可以做,但是假设我有1000000个元素,只弹出前三个最小的元素,那么就要用到大小为1000000的堆。这么做空间复杂度太高,不建议用这种方法。 思路三: 我们需要得到三个最小的元素,那么就建一个大小为3的堆,假设目前的堆结构中刚好放满了3个元素,那么这三个元素就是当前最小的三个元素。假设第四个元素是我们想要的元素之一,那么前三个至少有一个元素不是我们想要的,就需要弹出,那么弹出谁呢? 我们要得到的是前三个最小的元素,所以当前堆结构中最大的元素一定不是我们想要的,所以这里我们建一个大根堆。弹出该元素,然后放入第四个元素,直到遍历完整个数组。 这样我们就得到了只含有前三个最小元素的堆,并且可以看到堆的大小一直都是3,而不是有多少数据就建多大的堆,然后再依次弹出元素就行了。 // 找前 k个最小的元素 public static int[] topK(int[] arr,int k){ // 创建一个大小为 k的大根堆 PriorityQueue maxHeap = new PriorityQueue(k,new Comparator() { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }); for (int i = 0; i < arr.length; i++) { if (i < k){ // 放入前 k 个元素 maxHeap.offer(arr[i]); }else{ // 从第 k+1个元素开始进行判断是否要入堆 if (maxHeap.peek() > arr[i]){ maxHeap.poll(); maxHeap.offer(arr[i]); } } } int[] ret = new int[k]; for (int i = 0; i < k; i++) { ret[i] = maxHeap.poll(); } return ret; }登录后复制以上就是Java中如何使用堆来解决Top-k问题?的详细内容,更多请关注php中文网其它相关文章! |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |