How to implement a minimum heap sort to find the kth smallest element?

Question

I've been implementing selection sort problems for class and one of the assignments is to find the kth smallest element in the array using a minimum heap. I know the procedure is:

• heapify the array
• delete the minimum (root) k times
• return kth smallest element in the group

I don't have any problems creating a minimum heap. I'm just not sure how to go about properly deleting the minimum k times and successfully return the kth smallest element in the group. Here's what I have so far:

 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;
 }

As I stated before, the minimum heap part works correctly. I understand what I what to do- it seems easy to delete the root k times but then after that what index in the array do I return... 0? This almost works- it doesn't worth with k = n or k = 1.Would the kth smallest element be in the Any help would be much appreciated!

Answer 1

The only array index which is meaningful to the user is zero, which is the minimum element. So, after removing k elements, the k'th smallest element will be at zero.

Probably you should destroy the heap and return the value rather than asking the user to concern themself with the heap itself… but I don't know the details of the assignment.

Note that the C++ Standard Library has algorithms to help with this: make_heap, pop_heap, and nth_element.