保持最大的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：數組基於的方法是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