0

我正在编写一个函数来使用堆排序对数组进行排序。到目前为止，我有：

template <typename Item, typename SizeType>
void heap_sort(Item data[], SizeType size) {
vector<int> v(data,data+size);
SizeType unsorted = size;

make_heap(v.begin(),v.end());

while(unsorted > 1) {
    --unsorted;
    swap(data[0], data[unsorted]);
    reheapify_down(data,unsorted);
}
}

和：

template <typename Item, typename SizeType>
void reheapify_down(Item data[], SizeType size) {
SizeType current(0), big_child;
bool heap_ok = false;

while(!heap_ok && 2*current+1 < size) {
    if(2*current+2 > size)
        big_child = 2*current + 1;
    else if(data[2*current+1] > data[2*current+2])
        big_child = 2*current+1;
    else
        big_child = 2*current + 2;

    if(data[current] < data[big_child]) {
        swap(data[current],data[big_child]);
        current = big_child;
    }
    else
        heap_ok = true;
}
}

当我运行程序时，它会输出一个错误排序的数组。有什么我遗漏的或我忽略的错误吗？

4

1 回答 1

0

只是一些建议。

首先，我会编写一个小型代理类，它只会让您在集合上使用基于 1 的索引。堆中使用的所有索引数学都假定基于 1 的索引，并且在一个地方补偿基于 0 的索引比在所有代码中要容易得多。就目前而言，我很难在索引之后确保您reheapify_down的正确性。这当然是正确的一般想法，但要确定所有数学运算都是正确的，需要做很多工作。

其次，我会写一个check_heap（或其他）你可以用来验证你make_heap和你的reheapify_down（顺便说一句，我会决定“make_heap”或“heapify”，所以名字可以是“make_heap”和“remake_heap”，或者“heapify”和“reheapify”）。

但是，除此之外，很难确定问题所在，尤其是因为您没有在make_heap问题中包含您的代码。如果它不能正常工作，其余的就没有希望了。

于 2012-12-06T21:54:26.940 回答