堆排序，堆“正确性”

Question

我的问题是堆是否“正确”。我有一个任务，要求我做堆排序，但首先使用现有数组构建堆。如果我查看一下平分码，它就会告诉我有一个确切的答案。T实现堆构建的方式得到了一个稍微不同的答案，但据我所知，根据定义，堆是堆，因此是正确的。

“正确”数组顺序是

{15, 12, 6, 11, 10, 2, 3, 1, 8}

但我得到

{15, 12, 10, 11, 2, 6, 3, 1, 8}

原始向量是

{2, 8, 6, 1, 10, 15, 3, 12, 11}

void HeapSort::buildHeap(std::vector<CountedInteger>& vector)
{    
std::vector<CountedInteger> temp;
for(int i = 0; i < vector.size(); i++)
{
    temp.push_back(vector[i]);
    fixDown(temp, i);

}
vector.swap(temp);
for(int i = 0; i < vector.size(); i++)
{
    std::cout<< vector[i]<<std::endl;

}
}

void HeapSort::sortHeap(std::vector<CountedInteger>& vector)
{
}

inline unsigned int HeapSort::p(int i)
{
    return ((i-1)/2);
}

void HeapSort::fixDown(std::vector<CountedInteger>& vector, int node)
{

if(p(node) == node) return;

if(vector[node] > vector[p(node)])
   {
       CountedInteger temp = vector[node];
       vector[node] = vector[p(node)];
       vector[p(node)] = temp;
       fixDown(vector, p(node));
    }

Answer 1

从数组中创建堆绝对是一种操作，可以产生多个不同但有效的堆。

如果您查看一个琐碎例子，很明显，至少有一个节点的一些子树可以切换位置。在给定的例子中，2和7可以转换位置。25和1还可以转换立场。如果堆的最小深度和最大深度相等，那么任何节点的子树都可以切换位置。

如果分级程序是自动的，则应该以一种检查堆属性的方式来实现它，而不是检查确切的数组。如果你的学分是老师，你应该在他们面前正式证明你的堆是正确的，这是微不足道的。