如何實現最小堆排序來查找第k個最小元素？

我已經實現選擇排序問題類和任務之一就是找到陣列中使用最小堆第k個最小元素。我知道程序是：如何實現最小堆排序來查找第k個最小元素？

heapify陣列
刪除該組中的最小（根）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個最小的元素將在任何幫助將非常感激！

這是對用戶有意義的

來源

2011-04-10 thomascirca

唯一的數組索引是零，這是最小的元素。所以，除去k元件之後，k「個最小的元素將是零。

也許你應該銷燬堆和返回值，而不是要求用戶與堆本身關心自理......但我不知道轉讓的細節。

請注意，C++標準庫的算法可以幫助您：make_heap,pop_heap和nth_element。

來源

2011-04-10 01:35:42 Potatoswatter

只是爲了防止任何可能的誤解：make_heap和pop_heap處理min_heap的。 nth_element不* *（它通常使用QuickSelect的中位數變量的中位數）。 – 2011-04-10 01:56:32

@Jerry：是的。 'nth_element'對給定的數組進行部分排序，並且可能比基於堆的方法快。 – Potatoswatter 2011-04-10 02:01:39

感謝您的回答。我無法使用C++ SL進行此任務。通過它，並意識到我的錯誤是 - 簡單的計數器調整！ – thomascirca 2011-04-10 23:40:09

如何實現最小堆排序來查找第k個最小元素？

回答

相關問題