当前位置: 首页 > >

堆排序以及TopK问题

发布时间:

堆排序

利用数组来实现堆,堆分为小顶堆和大顶堆


小顶堆:父亲节点的值小于左右孩子节点


大顶堆:父亲节点的值大于左右孩子节点?


如果是对数组从小到大排序


(1)为数组构建一个初始大顶堆,则数组的第一个元素就是数组最大的元素


(2)循环N-1一次,每次把数组的最后一个元素与数组第一个元素交换,然后数组长度从后减1,再对新的数组重复第一步,然后在重复第二步,知道数组的长度为1


package xidian.lili.topk;

public class HeapSort {
/**
* 从小到大排序,需要构建大顶堆
* @param arr
*/
public static void HeapSort(int arr[]){
//用数组存储堆,从arr.length/2+1开始到后面的节点都是叶子节点
//所以从arr.length/2往前构造大顶堆
int len=arr.length;
for(int i=arr.length/2;i>0;i--){
heapAdjust(arr,i,arr.length);
}

//排序交换第一个元素和最后一个元素,循环n-1次
for(int i=arr.length-1;i>0;i--){
int temp=arr[i];
arr[i]=arr[0];
arr[0]=temp;
heapAdjust(arr,0, i);
}
}
/**
* 对于当前的parent节点(不是叶子节点),调整结构,使得满足大顶堆结构
* @param arr
* @param parent
* @param length 在排序阶段,每次把堆顶元素和最后一个元素交换,把剩下的元素重新构造对,长度每次减少1
*/
private static void heapAdjust(int[] arr, int parent, int length) {
int temp=arr[parent];
int child=parent*2+1;
while(child if(child+1arr[child]){//左右孩子比较
child=child+1;
}
if(temp>arr[child]){
break;
}
arr[parent]=arr[child];
parent=child;
child=parent*2+1;

}
arr[parent]=temp;

}
public static void main(String[] args) {
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
HeapSort(arr);
for(int i:arr){
System.out.println(i);
}

}

}

利用堆结构解决TopK的问题,被腾讯的面试官问过一次,有很大的一堆数设为N,然后我们要得到这N个数字中最大的K个数


思路1

(1)首先选取这一堆数字的前k个存到一个k大小的数组


(2)把这长度为k的数组构建成一个小顶堆,也就是数组的第一个元素始终是这个数组中最小的数字


(3)然后对于剩下的N-K和数字遍历,每次比较这个数字与k大小数组的第一个数字,如果比它大,就交换,然后读修改以后的K大小的数组重新进行最小堆的结构调整。一直到把这N和数字遍历完,K大小的数组就是这N个数字中最大的K个


优点:空间复杂度低,每次只需要维护k大小的数组满足最小堆结构


package xidian.lili.topk;

import javax.swing.text.DefaultEditorKit.InsertBreakAction;

//返回一堆数字中最大的k个数字
public class TopK {
public static void main(String[] args) {
int[] arr = { 9, 3, 7, 6, 5, 4, 8, 2, 1, 0 };
int []res= getTopK(arr,3);
for(int i:res){
System.out.println(i);
}

}
/*
* 创建k个元素的小顶堆
*/
public static int[] creat(int arr[],int k){
int res[]=new int [k];
for(int i=0;i res[i]=arr[i];
}
for(int i=k/2;i>=0;i--){
int temp=res[i];
int child=i*2+1;
while(child if(child+1 child++;
}
if(temp break;
}
res[i]=res[child];
i=child;
child=child*2+1;
}
res[i]=temp;
}

return res;
}
private static int [] getTopK(int arr[],int k){
int res[]=creat(arr,k);//k个元素的小顶堆
int min=res[0];
for(int i=k+1;i if(arr[i]>min){
insert(res,arr[i]);
}
}
return res;
}
private static void insert(int[] res, int value) {
res[0]=value;
for(int i=res.length/2;i>=0;i--){
int temp=res[i];
int child=i*2+1;
while(child if(child+1 child++;
}
if(temp break;
}
res[i]=res[child];
i=child;
child=child*2+1;
}
res[i]=temp;
}

}

}


?


思路2:利用优先队列

这里我们利用优先队列构建大顶堆,解决求topK小的问题?


优先队列在添加元素的时候是升序的,所以我们根据比较器改变比较规则


package xidian.lili.topk;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
//利用优先队列构件大顶堆,解决topk小
public class PriorityQueueForTopK {

private PriorityQueue queue;
private int maxSize;
public PriorityQueueForTopK (){ }
public PriorityQueueForTopK (int maxSize){
this.maxSize=maxSize;
this.queue=new PriorityQueue(maxSize,new Comparator(){

@Override
public int compare(E o1, E o2) {
return o2.compareTo(o1);//优先队列默认是升序,这样是降序,构造大顶堆
}
});
}
public void add(E e){
if(queue.size() queue.add(e);
}else{
if(e.compareTo(queue.peek())<0){
queue.poll();
queue.add(e);
}
}
}
//优先队列本来时无序的,可以用list来包装,或者可以每次poll()方法取出数据是有序的
public List sortedList(){
List list=new ArrayList<>(queue);//用list来包装queue,可以调用结合排序
Collections.sort(list);
return list;
}
public static void main(String[] args) {
//选出前10个
PriorityQueueForTopK priorityQueueForTopK=new PriorityQueueForTopK<>(10);
Random random=new Random();
for(int i=100;i>=0;i--){
//System.out.print(random.nextInt(1000)+" ");
//priorityQueueForTopK.add(random.nextInt(1000));
priorityQueueForTopK.add(i);

}

//for(Integer i:priorityQueueForTopK.sortedList()){
//System.out.println(i);
//}
while(!priorityQueueForTopK.queue.isEmpty()){
System.out.println(priorityQueueForTopK.queue.poll());
}
}

}


topK频率最大的字符串

对于topk问题引申,比如我们在微博上的热门,就是把每次用户搜索的字符串记录下来,热门10分钟更新一次,假设这10分钟内有一千万个记录,我们从这一千万个数据中,找出出现次数最大的10个字符串,那么可以用HashMap加堆来实现。


(1)创建一个HashMap,key代表查询的字符串,value是次数的hash表,插入记录


(2)维护一个大小为K的小顶堆,初始k大小的数组是从hash表中遍历到K的记录,然后继续遍历,每次把得到的元素与堆顶元素,过程就是基于小顶堆topK的过程



topK如果数据量太多,一个数组存不下,可以利用数据的个数N%n,利用这样hash把数据分成n小份,然后每一份又是topK的问题了,然后对于结果就是k*n的数据量,再合起来求topK



友情链接: