Java最小ヒープTopK問題の解決

TopK問題とは,大量のデータ(ソースデータ)から最大(または最小)のK個のデータを取得することである.
TopK問題はよくある問題です.例えば、学校は全校生徒の中で最も成績の高い500人の学生を見つけ、ある検索エンジンは毎日100件の検索回数が最も多いキーワードを統計します.
この問題に対して、解決方法はたくさんあります.
方法1:ソースデータ中のすべてのデータをソートし、前のK個のデータを取り出すのがTopKである.
しかし,データ量が大きい場合,k個の最大数しか必要とせず,全体的なソートに時間がかかり,効率は高くない.
方法2:K長の配列a[]を維持し、ソースデータの前K個を読み出して配列を入れ、その配列を昇順に並べ替え、ソースデータのK個目以降のデータを順次読み出し、配列中の最小の要素(a[0])と比較して、a[0]より小さい直接pass、より大きい場合は、最小の要素a[0]を破棄し、二分法によりその位置を見つけ、その位置前の配列要素はソースデータの読み取りが終了するまで全体的に前方にシフトする.
これは方法よりも効率が大きく向上するが,Kの値が大きい場合,長さKのデータ全体がシフトするのも非常に時間がかかる.
この問題に対して,比較的効率の高い解決法は最小スタックを用いることである.
最小ヒープ(小根ヒープ)は、まず完全なツリーであり、すべての親ノードの値が2つのサブノードの値以下であるデータ構造です.
最小スタックのストレージ構造(物理構造)は、実際には配列です.次の図に示します.
スタックにはいくつかの重要な操作があります.
BuildHeap:通常の配列をスタックに変換し、変換が完了すると、配列はスタックの特性に合致します.すべての親ノードの値は2つのサブノードの値以下です.
Heapify(int i):元素iの左右のサブツリーが小根スタックである場合、Heapifyによりi元素をスタックの性質に適合するように適切な位置に降下させる.
上のTopK問題に戻り,最小スタックで解決する方法は,まずソースデータ中のK個の要素をK長の配列に配置し,配列を最小スタックに変換することである.さらに、ソースデータのK個以降のデータを順に取り、スタックのルートノード(配列の最初の要素)と比較し、最小スタックの性質によってルートノードは必ずスタックの中で最小の要素であり、それより小さい場合は直接pass、より大きい場合は要素を置き換え、ソースデータの遍歴が終わるまでルート要素をHeapifyする.
最小ヒープの実装:

public class MinHeap
{
	//        -   
	private int[] data;
	
	//            ，         
	public MinHeap(int[] data)
	{
		this.data = data;
		buildHeap();
	}
	
	//          
	private void buildHeap()
	{
		//                  (data.length) / 2 - 1         ，      。
		// *       ，   10   ， (data.length) / 2 - 1   4，a[4]     ， a[5]  *
        for (int i = (data.length) / 2 - 1; i >= 0; i--) 
        {
        	//          heapify
            heapify(i);
        }
    }
	
	private void heapify(int i)
	{
		//            
        int l = left(i);  
        int r = right(i);
        
        //         ，      、   、              
        int smallest = i;
        
        //      ，             
        if (l < data.length && data[l] < data[i])  
        	smallest = l;  
        
        //      ，                
        if (r < data.length && data[r] < data[smallest])  
        	smallest = r;  
        
        //             ，  return，      
        if (i == smallest)  
            return;  
        
        //                  ，          
        swap(i, smallest);
        
        //              ，             heapify
        heapify(smallest);
    }
	
	//           
	private int right(int i)
	{  
        return (i + 1) << 1;  
    }   

	//           
    private int left(int i) 
    {  
        return ((i + 1) << 1) - 1;  
    }
    
    //       
    private void swap(int i, int j) 
    {  
        int tmp = data[i];  
        data[i] = data[j];  
        data[j] = tmp;  
    }
    
    //           ，   
    public int getRoot()
    {
    	    return data[0];
    }

    //      ，   heapify
	public void setRoot(int root)
	{
		data[0] = root;
		heapify(0);
	}
}

最小ヒープによるTopKの取得:

public class TopK
{
	public static void main(String[] args)
	{
		//    
		int[] data = {56,275,12,6,45,478,41,1236,456,12,546,45};
		
//   Top5
		int[] top5 = topK(data, 5);
		
		for(int i=0;i<5;i++)
		{
			System.out.println(top5[i]);
		}
	}
	
	//  data        k  
	private static int[] topK(int[] data,int k)
	{
		//   K         topk 
		int[] topk = new int[k]; 
		for(int i = 0;i< k;i++)
		{
			topk[i] = data[i];
		}
		
		//       
		MinHeap heap = new MinHeap(topk);
		
		//  k  ，  data
		for(int i= k;i root)
			{
				heap.setRoot(data[i]);
			}
		}
		
		return topk;
}
}

作者:叉叉哥转载请注明出典:http://blog.csdn.net/xiao__gui/article/details/8687982