如何实现最小堆排序以找到第k个最小元素?
我一直在为类实现选择排序问题,其中一个任务是使用最小堆找到数组中的第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个最小元素在任何帮助中将非常感激!
没有找到相关结果
已邀请:
2 个回复
怪酞撩匹
元素后,
'最小元素将为零。 可能你应该销毁堆并返回值而不是要求用户关心堆本身...但我不知道赋值的细节。 请注意,C ++标准库具有以下算法:
,
和
。
版萍层分
时间。 第二个最小值就是此跳过列表中第一个节点的值。 重复上述步骤,直到获得所有k个最小元素。整体时间复杂度为
。形成堆需要时间n,因此总体时间复杂度为
。 还有一种方法是不使用Quickselect堆,其平均时间复杂度为O(n),但最差情况为
。 两种方法之间的显着差异在于第一种方法使所有k个元素最小到第k个最小值,而quickSelect仅给出第k个最小元素。 记忆方面,前一种方法使用
额外空间,quickSelect使用
。