고정 크기 정렬 된 트리의 데이터 구조를 기억할 수 없다.

Question

임의의 수의 레코드 중에서 가장 낮은 값을 찾고 싶다고 가정 해 봅시다. 레코드를 반복하면서 레코드가 최대 크기 인 10에 도달 할 때까지 구조에 추가합니다. 그 다음에 목록의 가장 높은 레코드보다 높지 않은 레코드를 추가 할 때마다 현재 가장 높은 레코드 최대 레코드 수를 유지하면서 제거됩니다.

또는 간단히 말해서 (얼마나 큰) 객체 목록을 처리하고 특정 수의 객체 만 메모리 효율적인 방식으로 유지합니까?

나는이 일을 할 수있는 일종의 데이터 구조가 있음을 기억하지만, 분명히 나는 ​​인터넷 검색의 부실한 일을하고있다. 나는 그것이 어딘가에 자바 구현을 갖게 될 어떤 구조를 가정한다.

Answer 1

다음 (예를 들면, binary heap) 그것은 max-heap을 구현하는 것 말고 할 수있는 간단한 방법 (의사 코드 어이!) :이 후

List elms; // original elements 
Heap heap; // heap we store in 

for element e in elms: 
    push e onto heap 
    if heap contains more than 10 elements: 
     pop the max element from heap 

, heap는 10 포함 가장 작은 요소.

바이너리 힙을 가정하면 tihs는 여분의 공간을 사용하고 O(n lg k) 시간을 소요합니다. 여기서 k은 원하는 요소의 수입니다.

Answer 2

N 값을 모두 메모리에 유지하려는 경우 이진 최소 힙을 사용하여 배열을 정리할 수 있습니다.

O (n) 상각 시간이 소요되며 10 개의 최소 요소를 취하여 O (10 * log (10)) 즉 O (1)을 취합니다.