如何实现最小堆排序以找到第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小的元素是否会在任何地方出现？非常感谢您的任何帮助！

- thomascirca

Answer 1

用户关心的唯一有意义的数组下标是零，它是最小元素。因此，在删除 k 个元素后，第 k 小的元素将位于零。

也许你应该销毁堆并返回值，而不是要求用户关注堆本身...但我不知道任务的详细信息。

请注意，C++标准库具有可以帮助实现此目的的算法：make_heap、pop_heap和nth_element。

- Potatoswatter

---

为了避免任何可能的误解：make_heap和pop_heap处理min_heap。nth_element不是（它通常使用QuickSelect的中位数变体）。 - Jerry Coffin

@Jerry：是的。nth_element 部分排序给定的数组，这可能比基于堆的方法更快。 - Potatoswatter

谢谢你的回答。我不能在这个任务中使用C++ SL。我已经解决了它，并意识到我的错误——简单的计数器调整！ - thomascirca

Answer 2

我不会提供详细的答案，只是解释如何在最小堆有序树中获取k个最小元素的关键点。这种方法使用跳表。

• 首先，形成一个跳表，其中节点仅包含一棵树的元素，该节点对应于堆的根。第一个最小元素就是存储在此节点中的值。
• 现在删除此节点，并将其子节点插入正确的位置，以保持值的顺序。此步骤需要O(logk)时间。第二个最小值就是此跳表中第一个节点中的值。

重复上述步骤，直到获得所有k个最小元素。总体时间复杂度为log(2)+log(3)+log(4)+... log(k) = O(k.logk)。形成堆需要n的时间，因此总体时间复杂度为O(n+klogk)。

还有一种不需要制作堆的方法，即Quickselect，其平均时间复杂度为O(n)，但最坏情况下为O(n^2)。

两种方法之间的显著差异在于，第一种方法将所有k个元素都赋予第k个最小值，而quickSelect仅返回第k个最小元素。从内存方面来看，前一种方法使用O(n)额外空间，而quickSelect则使用O(1)。

- Vishwajeet

---

如果你已经有了二叉堆，为什么还要制作跳跃表呢？ - Sneftel