TopN问题

从1000个数中选择前50个大的数

TopN问题：
堆排序思想：先从数组中选出前n个元素组成小根堆。然后遍历后续元素，如果小于堆顶，则跳过（要找的是较大的元素）。如果大于堆顶，则和堆顶元素交换，并将堆调整为小根堆

public void makeHeap(int[] a,int n){
        for(int i=n/2-1;  i>=0;i--){
            adjust(a,i,n);
        }
    }

    /**
     * @param a
     * @param i
     * @param n
     *<p>Description:小根堆 </p>  
     */
    private void adjust(int[] a, int i, int n) {
        int j=2*i+1;
        while(j<n){
            if(j+1<n && a[j]>a[j+1]){
                j++;
            }//选取左右孩子中较小的
            if(a[i]>a[j]){
                swap(a,i,j);
            }
            else{
                break;
            }
            i=j;
            j=2*i+1;
        }
    }

    
    public void topN(int [] a,int n){
        makeHeap(a, n);

        for(int i=n;i<a.length;i++){
            if(a[i]<=a[0]){
             continue;
            }
            else{
                swap(a, i, 0);
                adjust(a,0,n);
            }
        }
    }

    /**
     * @param a
     * @param i
     * @param j
     *<p>Description: </p>  
     */
    private void swap(int[] a, int i, int j) {
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
        
    }
    /**
     * 
     * @param a
     * @param n
     *<p>Description:堆排序 （这部分可忽略）</p>
     */
    public void HeapSort(int[] a,int n){
        
        makeHeap(a, n);
        for(int i=n-1;i>=0;i--){
            swap(a,0,i);
            adjust(a, 0, i);
        }
    }