最大10個の数字を保持する

Question

データセットを反復処理する間に、これまでの上位10個の番号のみをソート順に追跡する最良の方法は何ですか？

ソリューション...一般的な最小値と最大ヒープを実装することになったが...彼らは、インターネット上のJavaライブラリであるか、または容易に入手できない悲しとして....コードではありませんgaurunteesは...

import java.util.ArrayList; 

public class MaxHeapGeneric <K extends Comparable> { 
    //ArrayList to hold the heap 
    ArrayList<K> h = new ArrayList<K>(); 
    public MaxHeapGeneric() 
    { 

    } 
    public int getSize() 
    { 
     return h.size(); 
    } 

    private K get(int key){ 
     return h.get(key); 
    } 


    public void add(K key){ 
     h.add(null); 
     int k = h.size() - 1; 
     while (k > 0){ 
      int parent = (k-1)/2; 
      K parentValue = h.get(parent); 
      //MaxHeap - 
      //for minheap - if(key > parentValue) 
      if(key.compareTo(parentValue) <= 0) break; 
      h.set(k, parentValue); 
      k = parent; 
     } 
     h.set(k, key); 
    } 
    public K getMax() 
    { 
     return h.get(0); 
    } 
    public void percolateUp(int k, K key){ 
     if(h.isEmpty()) 
      return ; 

     while(k < h.size() /2){ 
      int child = 2*k + 1; //left child 
      if( child < h.size() -1 && (h.get(child).compareTo(h.get(child+1)) < 0) ) 
      { 
       child++; 
      } 

      if(key.compareTo(h.get(child)) >=0) break; 

      h.set(k, h.get(child)); 
      k = child; 
     } 
     h.set(k, key); 
    } 
    public K remove() 
    { 
     K removeNode = h.get(0); 
     K lastNode = h.remove(h.size() - 1); 
     percolateUp(0, lastNode); 
     return removeNode; 
    } 
    public boolean isEmpty() 
    { 
     return h.isEmpty(); 
    } 

    public static void main(String[] args) 
    { 
     MaxHeapGeneric<Integer> test = new MaxHeapGeneric<Integer>(); 

     test.add(5); 
     test.add(9); 
     test.add(445); 
     test.add(1); 
     test.add(534); 
     test.add(23); 

     while(!test.isEmpty()) 
     { 
      System.out.println(test.remove()); 
     } 

    } 

} 

そして分ヒープ

import java.util.ArrayList; 


public class MinHeapGeneric <K extends Comparable> { 
    //ArrayList to hold the heap 
    ArrayList<K> h = new ArrayList<K>(); 
    public MinHeapGeneric() 
    { 

    } 
    public int getSize() 
    { 
     return h.size(); 
    } 

    private K get(int key){ 
     return h.get(key); 
    } 


    public void add(K key){ 
     h.add(null); 
     int k = h.size() - 1; 
     while (k > 0){ 
      int parent = (k-1)/2; 
      K parentValue = h.get(parent); 
      //for minheap - if(key > parentValue) 
      if(key.compareTo(parentValue) > 0) break; 
      h.set(k, parentValue); 
      k = parent; 
     } 
     h.set(k, key); 
    } 
    public K getMax() 
    { 
     return h.get(0); 
    } 
    public void percolateUp(int k, K key){ 
     if(h.isEmpty()) 
      return ; 

     while(k < h.size() /2){ 
      int child = 2*k + 1; //left child 
      if( child < h.size() -1 && (h.get(child).compareTo(h.get(child+1)) >= 0) ) 
      { 
       child++; 
      } 

      if(key.compareTo(h.get(child)) < 0) break; 

      h.set(k, h.get(child)); 
      k = child; 
     } 
     h.set(k, key); 
    } 
    public K remove() 
    { 
     K removeNode = h.get(0); 
     K lastNode = h.remove(h.size() - 1); 
     percolateUp(0, lastNode); 
     return removeNode; 
    } 
    public boolean isEmpty() 
    { 
     return h.isEmpty(); 
    } 

    public static void main(String[] args) 
    { 
     MinHeapGeneric<Integer> test = new MinHeapGeneric<Integer>(); 

     test.add(5); 
     test.add(9); 
     test.add(445); 
     test.add(1); 
     test.add(534); 
     test.add(23); 

     while(!test.isEmpty()) 
     { 
      System.out.println(test.remove()); 
     } 

    } 

} 

Answer 1

上位10項目を追跡するために、最小ヒープ（プライオリティキュー）を使用します。バイナリヒープの場合、時間の複雑さはO（N log M）であり、Nはアイテムの数であり、Mは10です。

トップアイテムを配列に格納するのに比べて、これは大きなM：arrayベースのアプローチはO（NM）です。リンクリストの場合も同様です。擬似コードで

：

heap = empty min-heap 
for each datum d: 
    heap.push(d) // add the new element onto the heap 
    if heap.size > 10: 
     heap.pop() // remove the smallest element 
    endif 
endfor 

今ヒープが10個の最大の項目が含まれています。ポップする：

while heap is not empty: 
    item = heap.top() 
    print item 
endwhile