최소 K 개수 찾기(더미로 구현)

가장 작은 K 개수를 찾거나 top K 문제를 찾는 흔한 문제최대 무더기를 구축하면 O(k+(n-k) logk) = O(n*logK) 시간 내에 실현할 수 있다.겸사겸사 최대 무더기를 복습해 봅시다.

    package    ;

public class MaxPQ >{
    private Key[] pq;
    private int N = 0;

    public MaxPQ(int maxN){
        //   1-N 
        pq = (Key[])new Comparable[maxN+1]; 
    }
    private boolean less(int i,int j){
        //         ,i   j   ，    true
        return pq[i].compareTo(pq[j]) < 0;  
    }

    private void exch(int i,int j){
        //           
        Key t =pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
    private void swim(int k){//        ，      ，  
        while(k > 1 && less(k/2,k)){
            exch(k/2,k);
            k = k/2;
        }
    }

    private void sink(int k){
        //           ，            ，       
        while(2*k <= N){
            int j = 2*k;
            if(j < N && less(j,j+1))
                j++; 
            if(!less(k,j))  //  k           ，    
                break;
            exch(k,j);
            k = j;
        }
    }

    public boolean isEmpty(){
        return N == 0;
    }

    public int size()
    {
        return N;
    }

    public void insert(Key v){
        pq[N++] = v;
        swim(N);
    }

    public Key delMax(){
        Key max = pq[1];
        exch(1,N--); //   ，   
        pq[N+1] = null;//      
        sink(1);
        return max;
    }

}

위의 코드는 비교적 완전하게 최대 무더기에 필요한 방법을 실현하였다.이렇게 하면 우리는 K개의 원소의 최대 더미를 유지하고 n-k개의 원소와 max를 비교한 다음에 작으면 이 원소를 삽입하고 그렇지 않으면 더미가 변하지 않는다.