Lucene3.0源码分析(二) Lucene中获得评分前N的DocumentID算法
?????? 本博客属原创文章,欢迎转载！转载请务必注明出处:http://guoyunsky.iteye.com/blog/723963
????? 本博客已迁移到本人独立博客: http://www.yun5u.com/
??????欢迎加入Heritrix群(QQ)：109148319,10447185? , Lucene/Solr群(QQ) :? 118972724??
????? 通过Lucene搜索返回的是评分(Score)前N的结果,默认是前100.这里我将这段算法复制下来,具体请看注释,同时这段算法不依赖Lucene任何组件,可以直接运行。
?
/** * 在一对数中找出前N个大的数,采用二叉堆 * 模仿Lucene中的获得评分前N的DocumentID * * @author Administrator * */public class LuceneFindTopN {private int[] heap; //存储数据private int size;//已存数据个数,也代表指针位置private int maxSize;//取前maxSize大的数private int minElement;//数据中最小的元素public LuceneFindTopN(int maxSize) {super();this.maxSize = maxSize;heap=new int[maxSize+1];size=0;minElement=0;}/** * 插入数据 * @param element * @return */public boolean insert(int element){if(size<maxSize){put(element);return true;}else if(size>0&&element>top()){ //大于最小的元素才进入,并调整数据顺序heap[1]=element;//替换头部元素(也就是最小的元素)为当前元素(因为当前元素比头部元素大)adjustTop();//调整头部元素return true;}else{return false;}}/** * 存入数据 * @param element */public void put(int element){size++;heap[size]=element;upheap();}/** * 返回top * @return */public int top(){if(size>0){return heap[1];}else{return 0;}}public int getSize() {return size;}public void setSize(int size) {this.size = size;}public final void upheap(){int i=size;int node=heap[i];int j=i>>>1;//父节点位置while(j>0&&node<heap[j]){//有父节点,并且要插入的数据比父节点的数据要小,则要交换位置heap[i]=heap[j];//该节点等于父节点数据i=j;//父节点指针位置j=j>>>1;//迭代父节点的父节点，以此类推}heap[i]=node;//要插入的数据放入合适位置}/** * 排放数据,从最小的元素开始排放,会删除该元素 * @return */public int pop(){if(size>0){int result=heap[1];//第一个元素作为结果返回,因为第一个元素最小heap[1]=heap[size];//第一个元素置为最大的元素heap[size]=-1;//最大的元素清空size--;//指针前移downHeap();return result;}else{return -1;}}public final void adjustTop(){downHeap();}public void downHeap(){int i = 1;int node = heap[i]; // 第一个元素,也就是刚插入的元素int j = i << 1; // 第二个元素int k = j + 1;// 第三个元素if (k <= size && heap[k]<heap[j]) { //如果当前数据大于等于3个,并且第三个数据小于第二个数据,则从第三个元素开始循环调整顺序,否则从第二个元素开始循环调整排序,如此可以少排一个并且可以扩容一倍j = k;}while (j <= size && heap[j]<node) {//一直循环，直到超出size(也就是数组大小)并且小于要插入的节点heap[i] = heap[j]; // 置换i = j;j = i << 1; //再乘以2(扩容一倍)k = j + 1; if (k <= size && heap[k]<heap[j]) { //没有超过size并且扩容一倍的数大于扩容一倍+1的数(也就是这2个数没有按照从小到大排序)，则从扩容点开始又重新计算j = k;//从扩容点}}heap[i] = node; //将最后一个调整顺序的数据的位置为要插入的数据的合适位置}public void print(){for(int i=1;i<=maxSize;i++){System.out.println(heap[i]);}}/** * @param args */public static void main(String[] args) {LuceneFindTopN find=new LuceneFindTopN(3);int[] source={44,65,23,45,55,78,21,32,43,876,1,66,13,35,38,96,437,55,980,21,1010,1001,1334,42,2354,7788,344,333,557,5454,7664,1235};for(int i=0;i<source.length;i++){/*int a=(int)(Math.random()*1000);*/int a=source[i];System.out.println(find.insert(a)+":"+a);}System.out.println("================================");/*find.print();*/int max=find.getSize();for(int i=0;i<max;i++){System.out.println(find.pop());}}}?
1 楼 linliangyi2007 2010-11-11 这个算法我是琢磨了一阵子了，发现它是一个不完全（非严格）的2叉树排序。