您的位置:首页 > 健康 > 美食 > 山东小语种网站建设_浙江省建设信息港网站_广州今日头条新闻_自己怎样推广呢

山东小语种网站建设_浙江省建设信息港网站_广州今日头条新闻_自己怎样推广呢

2024/10/31 9:16:19 来源:https://blog.csdn.net/ijj_zZ/article/details/143222444  浏览:    关键词:山东小语种网站建设_浙江省建设信息港网站_广州今日头条新闻_自己怎样推广呢
山东小语种网站建设_浙江省建设信息港网站_广州今日头条新闻_自己怎样推广呢

堆排序和Top-K问题

  • 1. 堆排序
  • 2. Top-K问题

1. 堆排序

堆排序是利用堆的性质进行排序的

  1. 如果需要升序,则建立大根堆
  2. 如果需要降序,则建立小根堆

下面以降序为例:
如果需要得到降序的结果,需要建立一个小根堆,将堆顶元素与最后一个元素交换(即将最大值放在数组最后),然后对新的堆顶元素进行向下调整;再将堆顶元素与倒数第二个元素交换(即将第二大的元素放在数组的倒数第二个位置),然后对新的堆顶元素进行向下调整;依次不断对堆进行调整

另外,如果按照这个思路,每次都会将一个“最小值”放到数组的末尾,那么去调整时,可能会将这个“最小值”调到其他位置去。因此,我们需要限制需要调整堆的范围,这时,就可以定义一个end变量记录需要调整堆的大小,也就是通过传参来限制usedSize的大小,从而限制向下调整堆的范围,每次将“最小值”放到数组末尾后,都将end–

本质上,就是将数组按照从后往前的顺序进行调整

那么问题来了,为什么进行降序时不建立大根堆?如果使用大根堆会怎样?
答: 如果建立大根堆,每次都能从栈顶拿到“最大值”,然后将其放到数组末尾,再进行调整。显然这样是无法在原数组基础上排序的,因为每次都把最大值放到了数组末尾。因此,如果建立大根堆来降序的话,必须额外去申请一块空间来存储每次拿到的“最大值”

例如:利用堆排序将数组{8,15,10,21,34,16,12}降序

在这里插入图片描述
在这里插入图片描述
代码实现:

    public void headSort() {int end = usedSize-1;while(end > 0) {int tmp = elem[end];elem[end] = elem[0];elem[0]= tmp;shiftDown(0, end);end--;}}

2. Top-K问题

TOP-K问题 即求数据集合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大,而K比较小

找到前K个最大的元素或者最小的元素,我们最容易想到的就是先将这些元素进行排序,但是当数据量较大时,这种方法就不可取了(可能数据都不能一下子全部加载到内存中),这时最佳的办法就是,利用堆来解决这个问题

基本思路:

  1. 找前K个最大元素,建小根堆
  2. 找前K个最小元素,建大根堆

下面以找前K个最大元素为例,拿出数组中前K个元素建立小根堆,将数组中剩下元素依次与堆顶元素对比,若比堆顶元素大,则将堆顶元素出出去,将它加入堆中,调整为小根堆。重复上述步骤,直至数组遍历完,这时小根堆里的元素即前K大元素,而堆顶元素时第K大元素

时间复杂度分析:

  • 前k个元素用向上调整建堆所用时间:Klog2K
  • 将数组中剩下元素加入堆并向上调整所用时间:(N-K)log2K
  • 总时间:Klog2K +(N-K)log2K = Nlog2 K
  • 由于K的值往往比较小,所以Nlog2 K约等于N,因此Top-K问题的时间复杂度为O(N)

例如:找出数组{0,1,2,3,4,5}中前k个最大元素

在这里插入图片描述

class Solution {class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o1.compareTo(o2);}}public int[] smallestK(int[] arr, int k) {int[] ret = new int[k];if (ret == null || k == 0) {return ret;}PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new IntCmp());for (int i = 0; i < k; i++) {priorityQueue.offer(arr[i]);}// K*logNfor (int i = k; i < arr.length; i++) {int peekVal = priorityQueue.peek();if (peekVal < arr[i]) {priorityQueue.poll();priorityQueue.offer(arr[i]);}}// (N-K)logNfor (int i = 0; i < k; i++) {ret[i] = priorityQueue.poll();}return ret;}
}

其实,优先级队列里建堆默认就是建小根堆,所以这里也可以不用写这个比较器

那么,现在自己来试一下找到前K小的元素吧!!!
OJ链接:面试题 17.14. 最小K个数

代码如下:

class Solution {class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}}public int[] smallestK(int[] arr, int k) {int[] ret = new int[k];if (ret == null || k == 0) {return ret;}PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new IntCmp());for (int i = 0; i < k; i++) {priorityQueue.offer(arr[i]);}// K*logNfor (int i = k; i < arr.length; i++) {int peekVal = priorityQueue.peek();if (peekVal > arr[i]) {priorityQueue.poll();priorityQueue.offer(arr[i]);}}// (N-K)logNfor (int i = 0; i < k; i++) {ret[i] = priorityQueue.poll();}return ret;}
}

找到前K小的元素需要建立大根堆,这时就需要手动地去写一个比较器了

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com