tree - 堆排序并向下渗透以获得最大堆
问题描述
我必须在 C++ 中为堆树类创建堆排序。我检查了任何参考,但所有参考都传递了参数。我们的代码如下所示:
template <typename Comparable>
vector<Comparable> heapsort()
我们必须创建heapsort
没有任何参数的函数。我尝试执行以下操作:
template <typename Comparable>
void heapsort(vector<Comparable> &array){
for (int i = (array.size()) / 2 - 1; i >= 0; i--)
{
percolateDown(i);
}
for (int j = array.size() - 1; j > 0; j--)
{
int temp = array[0];
array[0] = array[j];
array[j] = temp;
percolateDown(0);
}
}
此外,对于 percolate 方法,我得到了很多关于 percolate 方法的参考资料,但每个参考资料都有 3 个参数,但我的程序应该只有 1 个参数。
以下是我关于渗透的代码:
template <typename Comparable>
void BinaryHeap<Comparable>::percolateDown(int hole)
{
int child;
Comparable tmp = std::move(array[hole]);
for (; hole * 2 <= currentSize; hole = child)
{
child = hole * 2;
// child: left child
// child + 1: right child
if (child != currentSize && array[child + 1] < array[child])
++child;
if (array[child] < tmp)
array[hole] = std::move(array[child]);
else
break;
}
array[hole] = std::move(tmp);
}
以下是我对上述内容的错误:
BinaryHeap.cpp: In function 'void heapsort(std::vector<Comparable>&)':
BinaryHeap.cpp:143:9: error: there are no arguments to 'percolateDown'
that depend on a template parameter, so a declaration
of 'percolateDown' must be available [-fpermissive]
143 | percolateDown(i);
| ^~~~~~~~~~~~~
------------------------------------------------------
BinaryHeap.cpp:143:9: note: (if you use '-fpermissive', G++ will accept
your code, but allowing the use of an
undeclared name is deprecated)
BinaryHeap.cpp:151:9: error: there are no arguments to 'percolateDown'
that depend on a template parameter, so a declaration
of 'percolateDown' must be available [-fpermissive]
151 | percolateDown(0);
这是一个编程作业;对此的任何提示或提示都会有所帮助。