유지하는 가장 큰 10 개 번호

Question

데이터 집합을 반복하는 동안, 정렬 된 순서로, 지금까지 오직 상위 10 개 번호를 추적하는 가장 좋은 방법은 무엇입니까?

솔루션 ... 같은 슬프게도 그들은 코드에 어떤 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 항목을 추적하는 분 - 힙 (우선 순위 큐)를 사용하여 A 최소 힙. 바이너리 힙의 경우 시간 복잡도는 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