小白道时尚
当前位置:首页 - 房产 >

堆的应用——解决topk问题

2019-10-13来源:中国企讯网

前两期我们简单了解了堆以及堆的一些基本操作。今天,我们来谈谈堆的实际应用,解决topk问题。

100亿个数中找出最小的前K个数

由于我们前两节以大堆进行研究的,而我们知道,大堆的堆顶元素是堆的最大值,这样,我们比较堆顶与插入值的大小,就可以将较小的值插入堆中,因此我们这期用他来解决最小topk问题。

首先,我们还是在topk中简单定义几个内容,保留上期堆中的几个东西。

import java.util.Arrays;
public class Topk {
private int[] data;

private int k;

private int size=0;
public Topk(int k) {
this.k=k;
data=new int[k];
}


/**
* 返回父节点下标
* @param i
* @return
*/
private int parent(int i) {
return (i - 1) >> 1;
}
/**
* 交换 数组下标为i ,j的俩元素
* @param i
* @param j
*/
private void exChange(int i, int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}

/**
* 上浮
* @param index
*/
public void shift_up(int index) {
// 根节点不存在上浮操作
if (index > 0) {
int parent = parent(index);
// 如果父亲节点比index的数值小,就交换二者的数值
if (data[parent] < data[index]) {
//交换父子节点
exChange(parent, index);
//递归调用
shift_up(parent);
}
}
}

/**
* 下沉
* @param index
*/
public void shift_down(int index) {
child=n+1;

if (data[n+1]
++child;
}
}
//有左孩子
else if ((n+2)==size) {
child=n+1;
}

//比较
if (data[index]
exChange(index, child);
//递归调用
shift_down(child);
}

}
/**
* 添加数据
* @return
*/
public int[] insert(int value) {
//新增一个节点
if (size
data[size++] = value;
shift_up(size-1);
}
return data;
}

/**
* 删除数据
* @return
*/
public int[] delete(int index) {
if (index+1>size)
return data;
exChange(index,size-1);
shift_down(index);
data[--size]=0;
return data;
}

}

其中说明下:k表示前多少个。保留插入和删除操作。简单的定义就完成了,接下来就是如何实现。

/**
* 添加数据
* @return
*/
public int[] add(int value) {
//新增一个节点
if (size
insert(value);
}else {
if (data[0]>value) {
delete(0);
insert(value);
}
}
return data;
}

关于topk插入,分为两个步骤:

1.比较堆中是否已经满了(达到k个)。如果不满,直接插入。

2.如果堆已经满了,比较堆顶与插入元素的大小,如果堆顶大于要插入的值,则删除堆顶,插入新值。

测试代码如下:

public static void main(String[] args) {
long a=System.currentTimeMillis();
Topk topk = new Topk(10);
for (int i = 1000000000; i >= 1; i--) {
topk.add(i);
}
System.out.println(Arrays.toString(topk.data));
long b=System.currentTimeMillis();
System.out.println("耗时:"+(b-a)+"毫秒");
}

控制台输出:

[10, 9, 6, 7, 8, 2, 3, 4, 5, 1]耗时:15616毫秒

与我们的期望值一样。

当然,解决最大top问题,就需要用到小堆,其实现基本思路也是一样的。扩展链接为二叉树实现方式,可以进行对比学习。

堆的应用——解决topk问题

转载文章地址:http://www.hwbdn.com/fangchan/49468.html
(本文来自小白道时尚整合文章:http://www.hwbdn.com)未经允许,不得转载!
标签:
网站简介 联系我们 网站申明 网站地图

版权所有:www.hwbdn.com ?2017 小白道时尚

小白道时尚提供的所有内容均是网络转载或网友提供,本站仅提供内容展示服务,不承认任何法律责任。