|
锁定老帖子 主题：基于最小堆（小根堆）的topn算法
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-05-27
最后修改：2011-06-14
topn指的是从已经存在的数组中，找出最大（或最小）的前n个元素。
topn算法实现思路（找最大的n个元素） 1：取出数组的前n个元素，创建长度为n的最小堆。 2：从n开始循环数组的剩余元素，如果元素(a)比最小堆的根节点大，将a设置成最小堆的根节点，并让堆保持最小堆的特性。 3：循环完成后，最小堆中的所有元素就是需要找的最大的n个元素。 代码如下：
import java.util.Comparator;
/**
* 堆数据结构应用实例
*
* @author Administrator
*
*/
public class HeapApp {
public static int[] toPrimitive(Integer array[]) {
if (array == null)
return null;
if (array.length == 0)
return new int[0];
int result[] = new int[array.length];
for (int i = 0; i < array.length; i++)
result[i] = array[i].intValue();
return result;
}
/**
* 1：取出数组的前n个元素，创建长度为n的最小堆。
* 2：从n开始循环数组的剩余元素，如果元素(a)比最小堆的根节点大，将a设置成最小堆的根节点，并让堆保持最小堆的特性。
* 3：循环完成后，最小堆中的所有元素就是需要找的最大的n个元素。
*
* @param array
* @param n
* @return
*/
public static int[] topn(int[] array, int n) {
if (n >= array.length) {
return array;
}
Integer[] topn = new Integer[n];
for (int i = 0; i < topn.length; i++) {
topn[i] = array[i];
}
Heap<Integer> heap = new Heap<Integer>(topn, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// 生成最大堆使用o1-o2,生成最小堆使用o2-o1
return o2 - o1;
}
});
for (int i = n; i < array.length; i++) {
int value = array[i];
int min = heap.root();
if (value > min) {
heap.setRoot(value);
}
}
// heap.sort();
return toPrimitive(topn);
}
public static void main(String[] args) {
int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 11, 9, 10, 100 };
array = new int[] { 101, 2, 3, 4, 5, 6, 7, 8, 11, 9, 10, 100 };
int[] result = topn(array, 5);
for (int integer : result) {
System.out.print(integer + ",");
}
}
}
heap的数据结构，支持最大堆，最小堆。
import java.util.Comparator;
/**
* 堆数据结构
*
* @author Administrator
*
*/
public class Heap<T> {
/**
* 以数组形式存储堆元素
*/
private T[] heap;
/**
* 用于比较堆中的元素。c.compare(根,叶子) > 0。
* 使用相反的Comparator可以创建最大堆、最小堆。
*/
private Comparator<? super T> c;
public Heap(T[] a, Comparator<? super T> c) {
this.heap = a;
this.c = c;
buildHeap();
}
/**
* 返回值为i/2
*
* @param i
* @return
*/
private int parent(int i) {
return (i - 1) >> 1;
}
/**
*
* 返回指定节点的left子节点数组索引。相当于2*(i+1)-1
*
*
* @param i
* @return
*/
private int left(int i) {
return ((i + 1) << 1) - 1;
}
/**
* 返回指定节点的right子节点数组索引。相当于2*(i+1)
*
* @param i
* @return
*/
private int right(int i) {
return (i + 1) << 1;
}
/**
* 堆化
*
* @param i
* 堆化的起始节点
*/
private void heapify(int i) {
heapify(i, heap.length);
}
/**
* 堆化，
*
* @param i
* @param size 堆化的范围
*/
private void heapify(int i, int size) {
int l = left(i);
int r = right(i);
int next = i;
if (l < size && c.compare(heap[l], heap[i]) > 0)
next = l;
if (r < size && c.compare(heap[r], heap[next]) > 0)
next = r;
if (i == next)
return;
swap(i, next);
heapify(next, size);
}
/**
* 对堆进行排序
*/
public void sort() {
// buildHeap();
for (int i = heap.length - 1; i > 0; i--) {
swap(0, i);
heapify(0, i);
}
}
/**
* 交换数组值
*
* @param arr
* @param i
* @param j
*/
private void swap(int i, int j) {
T tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
/**
* 创建堆
*/
private void buildHeap() {
for (int i = (heap.length) / 2 - 1; i >= 0; i--) {
heapify(i);
}
}
public void setRoot(T root) {
heap[0] = root;
heapify(0);
}
public T root() {
return heap[0];
}
/**
* 取出最大元素并从堆中删除最大元素。
*
* @param
* @param a
* @param comp
* @return
*/
// public T extractMax(T[] a, Comparator<? super T> comp) {
// if (a.length == 0) {
// throw new
// IllegalArgumentException("can not extract max element in empty heap");
// }
// T max = a[0];
// a[0] = a[a.length - 1];
// heapify(0, a.length - 1);
// return max;
// }
/**
* @param args
*/
public static void main(String[] args) {
Integer[] temp = null;
temp = new Integer[] { 5, 2, 4, 6, 1, 3, 2, 6 };
temp = new Integer[] { 16, 14, 8, 7, 9, 3, 2, 4, 1 };
Comparator<Integer> comp = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
};
//创建最大堆
Heap<Integer> heap = new Heap<Integer>(temp, comp);
// heap.buildHeap();
for (int i : temp) {
System.out.print(i + " ");
}
System.out.println();
heap.sort();
for (int i : temp) {
System.out.print(i + " ");
}
System.out.println();
}
}
通过Comparator控制堆的性质（是最大堆还是最小堆） 创建最大堆
Heap<Integer> heap = new Heap<Integer>(topn,new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
//生成最大堆使用o1-o2,生成最小堆使用o2-o1
return o1-o2;
}
});
创建最小堆
Heap<Integer> heap = new Heap<Integer>(topn,new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
//生成最大堆使用o1-o2,生成最小堆使用o2-o1
return o2-o1;
}
});
如果有什么问题或更好的方法还请批评指正。 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2011-06-12
private void buildHeap() {
for (int i = (heap.length) / 2 - 1; i >= 0; i--) { } 楼主是不是i开始的下标不对啊？？ 还有就是left(i)和right(i)的赋值好像也有问题，？？？不知道是我理解错了？还是什么？ 望楼主解答！ |
| 返回顶楼 | |
|
发表时间：2011-06-14
最后修改：2011-06-14
tengyue5i5j 写道 private void buildHeap() {
for (int i = (heap.length) / 2 - 1; i >= 0; i--) { } 楼主是不是i开始的下标不对啊？？ 还有就是left(i)和right(i)的赋值好像也有问题，？？？不知道是我理解错了？还是什么？ 望楼主解答！ 构建堆时，只需要循环非叶子节点就行了。如果你觉得有错，请指明错在哪里，谢谢。 在实现left和right方法时，使用移位代替的乘法，目的是为了提高效率。代码的上的javadoc不正确。现在已经作修改。 left和right代码复杂的原因是，java数组下标是从0开始，元素0的left子节点是1，right子节点是2。通过表达式计算就是 (i+1)*2-1,使用移位的方式就是((i+1)<<1)-1 |
| 返回顶楼 | |
|
发表时间：2011-06-15
lotusyu 写道 tengyue5i5j 写道 private void buildHeap() {
for (int i = (heap.length) / 2 - 1; i >= 0; i--) { } 楼主是不是i开始的下标不对啊？？ 还有就是left(i)和right(i)的赋值好像也有问题，？？？不知道是我理解错了？还是什么？ 望楼主解答！ 构建堆时，只需要循环非叶子节点就行了。如果你觉得有错，请指明错在哪里，谢谢。 在实现left和right方法时，使用移位代替的乘法，目的是为了提高效率。代码的上的javadoc不正确。现在已经作修改。 left和right代码复杂的原因是，java数组下标是从0开始，元素0的left子节点是1，right子节点是2。通过表达式计算就是 (i+1)*2-1,使用移位的方式就是((i+1)<<1)-1 恩，现在看明白了，那天没怎么理解，所以理解下标有点错了，不好意思，学习了！ |
| 返回顶楼 | |
|
发表时间：2011-07-18
我想知道的是，当堆满的时候，你添加一个最大的，同时也得删掉一个最小的，怎么找到这个最小的呢？对堆再排序？开销太大了吧？
|
| 返回顶楼 | |
|
发表时间：2011-07-24
teasp 写道 我想知道的是，当堆满的时候，你添加一个最大的，同时也得删掉一个最小的，怎么找到这个最小的呢？对堆再排序？开销太大了吧？ 如果要找最大的10个元素，那么创建的是小根堆。小根堆的特性是根节点是最小元素。 不需要对堆进行再排序，当堆的根节点被替换成新的元素时，需要进行堆化，以保持小根堆的特性。 |
| 返回顶楼 | |
|
发表时间：2011-07-27
最后修改：2011-07-27
lotusyu 写道 teasp 写道 我想知道的是，当堆满的时候，你添加一个最大的，同时也得删掉一个最小的，怎么找到这个最小的呢？对堆再排序？开销太大了吧？
如果要找最大的10个元素，那么创建的是小根堆。小根堆的特性是根节点是最小元素。 不需要对堆进行再排序，当堆的根节点被替换成新的元素时，需要进行堆化，以保持小根堆的特性。 那么，堆化耗时多少呢？这个算法的时间复杂度大概是什么？ |
| 返回顶楼 | |
|
发表时间：2011-07-27
另外，想起来一个类似的共25匹马赛最快5匹马的问题（http://www.iteye.com/topic/255969），呵呵。
|
| 返回顶楼 | |
|
发表时间：2011-07-27
TOPN的，我也写了个
import java.util.Random;
public class TopN {
private int[] arr=null;
private int top;
private int setCount=0;
private Random random;
public TopN(){
this(100);
}
public TopN(int top){
this.top =top;
init();
}
private void init(){
arr = new int[top];
random = new Random();
for(int i=0;i<top;i++){
arr[i] = Integer.MIN_VALUE;
}
}
public boolean compare(int index,int value){
if(arr[index]<value){
return true;
}else{
return false;
}
}
public void setValue(int index,int value){
this.arr[index] =value;
}
public void setInMax(int value){
this.arr[setCount++] =value;
if(setCount == top){
this.heap();
}
}
public boolean isMaxSetCount(){
return setCount>=top;
}
public int getNextInt(){
int i = this.random.nextInt();
return i;
}
public void heap(){
int length =arr.length;
int t= (length-1)>>1;
for(int i=t;i>=0;i--){
minHeapify(arr,i,length);
}
}
private void minHeapify(int[] array,int i,int size){
int l = ((i<<1)+1);
int r = l+1;
int min = i;
if(l<size && this.compare(l, arr[min])){
min = l;
}
if(r<size && this.compare(r, arr[min])){
min = r;
}
if(min != i){
swap(array,min,i);
if(min<size-1){
minHeapify(array, min, size);
}
}
}
private void swap(int[] array,int i,int j){
array[i]^=array[j];
array[j]^=array[i];
array[i]^=array[j];
}
public void print(){
int j=0;
for(int i : arr){
++j;
System.out.print(i+",");
if(j>=10){
System.out.println();
j=0;
}
}
System.out.println();
}
public static void main(String[] args){
long start =System.nanoTime();
TopN t100 = new TopN(100);
for(long i=0;i<100000000;i++){
int tmp = t100.getNextInt();
if(!t100.isMaxSetCount()){
t100.setInMax(tmp);
}else if(t100.compare(0, tmp)){
t100.setValue(0, tmp);
t100.heap();
}
}
long end = System.nanoTime();
t100.print();
System.out.println("Used time:"+(end-start)/1000000+" ms");
}
}
|
| 返回顶楼 | |
|
发表时间：2011-09-22
直接快速排序，再取topN
Arrays.sort(arr); 不知道会不会更快一点 |
| 返回顶楼 | |
