c++筛选堆

发布于 2024-10-05 08:40:50 字数 436 浏览 1 评论 0原文

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

该函数正在传递我的向量，它当然是堆、根的位置，然后是 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;
}

知道出了什么问题吗？

原文

I am writing a program that requires me to use a heap, and everything runs fine besides my sorting methods, obviously quite important! I am not sure what is wrong with my logic or if I am missing something stupid. But a fresh set of eyes to look at this would be nice.

The function is being passed my vector which is of course the heap, the location of the root, and then either the STL less or greater as a predicate.

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;
}

Any idea what is wrong?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

愁杀 2024-10-12 08:40:50

向量中的第一个元素位于 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]) 是否为 true。如果 func 是堆条件，您可能想检查这是否为 false...

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

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

The first element in a vector is at v[0]. You seem to assume it's at v[1]. Is there a reason for this?

If the root is at v[0], given a node at index i, the parent is at int((i-1)/2) (though (i-1)>>1 might be more efficient), and the children are at 2i+1, 2i+2. E.g.:

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

On the other hand, if the root is at v[1], the parent is at int(i/2) (or i>>1), and the children are at 2i, 2i+1. E.g.:

     1
   2   3
 4  5 6  7
89 AB CD EF

So that could be an issue.

You check to see if func(x, v[start/2]) is true. If func is the heap condition, you may want to check if that's false...

Is the vector already large enough to include v[start]? If upheap() is being used to add items into the heap one at a time... And the vector's size is never increased... (Also, you are starting at v[1], not v[0]. So that's an extra element.)

Have you tried writing a simple scaffolding (code that is used for testing/debugging but not part of the final product) routine to print the heap, adding it into your loop, and running with practice data to see where things go off kilter?

回复收藏 0 原文

~没有更多了~