堆积故障

Question

最近我在这里发布了一个关于*的问题Time complexity issues with multimap 我得到了一些很好的答案，它提到了堆的使用，这在我以前从未使用过。我创建了一个使用minheap和maxheap重写的新程序。它的效果很好，它比我为这个问题实施的其他任何程序都快得多。唯一的问题是偶尔会抛出一些错误的答案。 我回去做了很多调试。我意识到问题出在我堆的组织中。它没有像我认为通过比较操作使用push_heap和pop_heap那样进行排序和分发。另外，当我尝试在Visual Studio上运行程序时，最终会看到很多断言错误被抛出。我尝试在cplusplus.com和cppreference.com上阅读更多关于堆和他们的方法。我想我可能不是正确理解某些东西，因此会遇到更多问题。

令我困惑的第一件事是push_heap。我的理解是这样的：push_heap有两个参数，并且通过默认它将至少值推到位置last-1。它只在第一个参数小于第二个参数时才这样做，否则它保持不变。它基本上保持了正常堆的顺序。第三个可选参数是一个比较运算符，它可以用作greater（），然后将较大的元素推到最后一个位置。

什么是没有意义的是，如果我有一个动态插入或删除矢量中进行的数字，我有问题保持此顺序。如果我想让矢量按升序排列，我会使用更大的操作来继续推堆，以使值增加。但它是混淆当你第一次看push_heap方法，因为它看起来很像一些其他的算法功能，这在范围内进行喜欢的数字，例如：

std::unique (myvector.begin(), myvector.end(), myfunction); 

这push_heap不做。它不会对全部这个比较操作进行范围内这个向量的数字，我最初并不明白。

在发现push_heap并未真正保持我的向量排序后，我不得不保留我的向量以便使用二分搜索。我使用sort_heap，但是这会减慢程序的速度，但速度不够快。

此外，我发现有时push_heap会在奇怪的场合抛出无效的堆错误。

例如像：

push_heap(v.begin(), v.end(), greater<int>()); 

与755，98，55载体，22

你push_heap后会看到：

 22, 98, 55, 755 

但让我们说，你有 22，98，55，755

通常它会继续前进，不会因为比较的虚假回报而进行任何推送。这是可以预料的。

但有时我会尽量push_heap上：

887，52，44，22

，它会说

 'invalid heap' 

，或者如果我尝试： 22，52 ，44，887，而不是只是返回false和移动它将打破

'invalid heap' 

这种情况有时也会发生在pop_heap上。

为什么我变得无效的堆？是否因为所有的堆必须按降序排列？

编辑：我发现这对cplusplus.com，这是我想回答一个问题：

The element with the highest value is always pointed by first. The order of the other elements depends on the particular implementation, but it is consistent throughout all heap-related functions of this header.

Answer 1

... push_heap有两个参数，默认情况下它推的最小值最后定位-1。它只在第一个参数小于第二个参数时才这样做，否则它保持不变。

没有。如果您的存储是一个矢量v，目前堆（如make_heap创建），你应该叫

v.push_back(new_item); 
push_heap(v.begin(), v.end()); 

添加一个新的项目。参见例如here或here。

考虑到push_heap实在需要（这是需要已经履行堆不变）的范围[begin, end-1)和在end-1所附元件（可能不是），并且直到堆不变恢复所有的最后一个元素向上移动[begin, end)。该算法被解释为here。

---

发现push_heap之后是不是真的让我的矢量分类...

堆不排序。他们有一个排序约束（the heap property），它是特别故意比更弱。

如果要执行二进制搜索，则需要一个完全排序的容器，使用sort_heap每次都是既缓慢和破坏性的堆转换为一个：你的容器是不是堆调用此之后的任何更多，你不能将它作为一个使用。现在

---

，你编辑：堆不必须按降序排列。最大堆按降序排列（前面最大的元素），最小堆以升序排列（前面最小的元素）。

默认在标准库中是建立一个最小堆，使用operator<进行比较。为了建立一个最大堆，你只需通过std::greater<int>或任何（可选）最后的参数。