최소 힙 정렬을 구현하여 k 번째 최소 요소를 찾는 방법은 무엇입니까?

Question

클래스에 대한 선택 정렬 문제를 구현했으며 할당 중 하나는 최소 힙을 사용하여 배열에서 k 번째로 작은 요소를 찾는 것입니다. 나는 절차는 알고

이

• 배열

내가 어떤 문제가 만드는이없는 그룹의 최소 (루트) K 시간

반환 k 번째 작은 요소를 삭제를 heapify 최소 힙. 나는 최소한 k times를 적절히 삭제하고 그룹에서 가장 작은 k 번째 요소를 성공적으로 반환하는 방법을 모를뿐입니다. 여기까지 내가 지금까지 가지고있는 것 :

bool Example::min_heap_select(long k, long & kth_smallest) const { 
//duplicate test group (thanks, const!) 
Example test = Example(*this); 

//variable delcaration and initlization 
int n = test._total ; 
int i; 

//Heapifying stage (THIS WORKS CORRECTLY) 
for (i = n/2; i >= 0; i--) { 
    //allows for heap construction 
    test.percolate_down_protected(i, n); 
}//for 


//Delete min phase (THIS DOESN'T WORK) 
for(i = n-1; i >= (n-k+1); i--) { 


    //deletes the min by swapping elements 
    int tmp = test._group[0]; 
    test._group[0] = test._group[i]; 
    test._group[i] = tmp;  

    //resumes perc down 
    test.percolate_down_protected(0, i);   


}//for 

    //IDK WHAT TO RETURN 
    kth_smallest = test._group[0]; 



void Example::percolate_down_protected(long i, long n) { 

//variable declaration and initlization:  
int currPos, child, r_child, tmp; 
currPos = i; 
tmp = _group[i]; 
child = left_child(i); 

//set a sentinel and begin loop (no recursion allowed) 
while (child < n) { 

    //calculates the right child's position 
    r_child = child + 1; 

    //we'll set the child to index of greater than right and left children 
    if ((r_child > n) && (_group[r_child] >= _group[child])) { 
     child = r_child; 
    } 
    //find the correct spot 
    if (tmp <= _group [child]) { 
     break; 
    } 

    //make sure the smaller child is beneath the parent 
    _group[currPos] = _group[child]; 

    //shift the tree down 
    currPos = child; 
    child = left_child(currPos); 
} 

//put tmp where it belongs 
_group[currPos] = tmp; 
} 

앞에서 언급했듯이, 최소 힙 부품은 올바르게 작동합니다. 내가 무엇을 해야할지 이해한다. 루트 k 번을 지우는 것이 쉽지만 배열의 어떤 인덱스를 반환 할 것인가 ... 0? 이것은 거의 작동합니다. k = n 또는 k = 1로 가치가 없습니다. k 번째 가장 작은 요소가 Any help에 있으면 많은 도움이됩니다!

Answer 1

사용자에게 의미있는 유일한 배열 인덱스는 0이며 최소 요소입니다. 따라서 k 개의 요소를 제거한 후 k '번째로 작은 요소는 0이됩니다.

아마 힙을 파기하고 힙 자체에 대해 사용자에게 묻는 대신 값을 반환해야하지만 할당의 세부 사항을 알 수는 없습니다.

C++ 표준 라이브러리에는 make_heap, pop_heap 및 nth_element과 같이 도움이되는 알고리즘이 있습니다.