2

我正在编写一个需要我使用堆的程序，除了我的排序方法之外，一切都运行良好，显然非常重要！我不确定我的逻辑有什么问题，或者我是否遗漏了一些愚蠢的东西。但是，如果有一双新的眼睛来看待这件事，那就太好了。

函数被传递给我的向量，它当然是堆、根的位置，然后是 STL less 或 greater 作为谓词。

template<class T,class P>
void upheap(vector<T>& v, int start, P func) {
   T x = v[start];
   while (start > 1 && func(x, v[start/2])) {
      v[start] = v[start/2]; start /= 2;
   }
   v[start] = x;
}

知道有什么问题吗？

4

1 回答 1

2

向量中的第一个元素位于 v[0] 处。您似乎认为它位于 v[1]。是否有一个原因？

如果根在 v[0]，给定索引 i 处的节点，则父节点位于 int((i-1)/2) （尽管 (i-1)>>1 可能更有效），子节点位于 2i+1, 2i+2。例如：

     0
   1   2
 3  4 5  6
78 9A BC DE

另一方面，如果根在 v[1]，则父在 int(i/2)（或 i>>1），子在 2i，2i+1。例如：

     1
   2   3
 4  5 6  7
89 AB CD EF

所以这可能是一个问题。

您检查func(x, v[start/2])是否为真。如果 func 是堆条件，您可能需要检查这是否为假...

向量是否已经足够大以包含 v[start]？如果 使用upheap()一次将项目添加到堆中...并且向量的大小永远不会增加...（另外，您从 v[1] 开始，而不是 v[0]。所以这就是一个额外的元素。）

您是否尝试过编写一个简单的脚手架（用于测试/调试但不是最终产品的一部分的代码）例程来打印堆，将其添加到循环中，并使用练习数据运行以查看哪里出了问题？

于 2010-12-03T05:32:25.910 回答