c++ - 堆排序，堆 "correctness"

Question

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

“正确的”数组顺序是

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

但是我明白了

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

原始 vector 为

{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

有许多可能的方法可以从输入创建最大堆。你举个例子:

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

它满足堆标准，所以它是一个正确的最大堆。另一个例子是:

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

这也满足堆准则，所以它也是一个正确的最大堆。

最大堆标准:每个节点都大于它的任何子节点。

一个更简单的例子是1, 2, 3，它有两个堆，

  3       3 / \     / \1   2   2   1