고정 정렬 된 목록/데이터 구조

Question

나는 다양한 객체의 성능을 기록하는 무언가를 쓰고 있습니다. 나는 가장 열악한 10 대시기를 찾고 싶다. 그러므로 고정 된 정렬 된 목록과 같은 것을 원합니다. 예를 들어서 제 경우에 10입니다. 그래서 새로운 시간이 생길 때마다 그냥 삽입하고 주문합니다. 그것은 고정 될 것이므로, 다섯 번째 시간을 삽입 한 후에 (아래의 예제에서 5로 제한된 것으로 가정하면) 목록은 증가하지 않을 것이지만 목록에 삽입하고 가장 작은 값을 제거합니다.

예.

var topTen = new XXX<double>(5); 

XXX.Insert(1); 
XXX.Insert(3); 
XXX.Insert(2); 
XXX.Insert(6); 
XXX.Insert(4); 
XXX.Insert(5); 

/* 
topTen[0] is 6 
topTen[1] is 5 
topTen[2] is 4 
topTen[3] is 3 
topTen[4] is 2 
*/ 

나는 그것을 위해 무언가를 쓸 예정 이었지만, 이미 무언가가 있는지 궁금합니다.

Answer 1

일반적으로 힙을 사용하여 이와 같은 작업을 수행합니다. 예를 들어

5 크기를 제한하고, 작업을 완료 할 때 순서로 상위 5 개를 얻을 수 있습니다

var heap = new BinaryHeap<int>(); 

for (int i = 0; i < 1000; ++i) 
{ 
    var time = GetTimeSomehow(); 
    if (heap.Count < 5) 
    { 
     heap.Insert(time); 
    } 
    else if (time > heap.Peek()) 
    { 
     // the new value is larger than the smallest value on the heap. 
     // remove the smallest value and add this one. 
     heap.RemoveRoot(); 
     heap.Insert(time); 
    } 
} 

: 닷넷에서 사용 가능한 힙 데이터 구조가 없습니다

while (heap.Count > 0) 
{ 
    var time = heap.RemoveRoot(); 
    Console.WriteLine(time); 
} 

뼈대. 나는 간단한 것을 간행했다. A Generic BinaryHeap Class을 참조하십시오.

Answer 2

이 (안된)를보십시오 listLength = 5

지능;

List<int> list = new List<int>(listLength+1); 

void VerifyTime(int time) { 
    list[listLength] = time; 
    var i = listLength; 
    while (listLength>0 && list[listLength] < list[listLength-1]) 
    swap(list, listLength, listLength-1); 
} 

void swap (List<int> l, int a, int b) { 
    var temp = l[a]; 
    l[a] = l[b]; 
    l[b] = temp; 
} 

ListLength의 작은 값의 경우는 잘 작동합니다.