如何实现最小堆排序以找到第k个最小元素？

Question

我一直在为类实现选择排序问题,其中一个任务是使用最小堆找到数组中的第k个最小元素.我知道程序是:

• 堆化数组
• 删除最小(根)k次
• 返回组中的第k个最小元素

创建最小堆我没有任何问题.我只是不确定如何正确删除最小k次并成功返回组中的第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个最小元素在任何帮助中将非常感激!

Answer 1

对用户有意义的唯一数组索引是零,这是最小元素.因此,在删除k元素后,k'最小元素将为零.

可能你应该销毁堆并返回值,而不是要求用户关心堆本身...但我不知道赋值的细节.

需要注意的是,C++标准库的演算法,以帮助这一点:make_heap,pop_heap,和nth_element.