c++ - 堆问题

Question

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

让我困惑的第一件事是 push_heap。我的理解是这样的:push_heap 有两个参数，默认 它将least 值推到 last-1 位置。它仅在第一个参数小于第二个参数时才这样做，否则保持不变。它基本上保持正常堆的顺序。第三个可选参数是一个比较运算符，它可以用作 greater() ，然后将更大的元素推到 last-1 位置。

没有意义的是，如果我在 vector 中动态插入或删除数字，我将无法保持此顺序。如果我希望 vector 按升序排列，我会使用更大的操作来继续插入堆，以便值升序。但是当您第一次看到 push_heap 方法时会感到困惑，因为它看起来很像其他一些算法函数，这些函数在 range 数字中执行，例如:

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

push_heap 不做。它不会对 vector 范围中的所有数字做这个比较操作，我一开始没看懂。

在发现 push_heap 并没有真正保持我的 vector 排序之后，我不得不保持我的 vector 排序以便使用二进制搜索。我使用了 sort_heap，但这会使程序变慢，速度不够快。

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

例如:

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

vector 为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 上找到了这个，我猜它回答了一个问题:

具有最高值的元素总是第一个指向。其他元素的顺序取决于特定的实现，但在该 header 的所有与堆相关的函数中都是一致的。

Answer 1

... push_heap has two arguments and by default it pushes the least value to position last-1. It only does this if the first argument is less than the second argument, otherwise it stays the same.

没有。如果你的存储是 vector 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 .

---

After finding that push_heap wasn't really keeping my vector sorted ...

堆没有排序。它们有一个排序约束 ( the heap property )，特别有意地弱于完全排序。

如果你想执行二进制搜索，你需要一个完全排序的容器，并使用 sort_heap 将你的堆转换为一个堆。每次都既缓慢又具有破坏性:调用此方法后，您的容器不再是堆，您不能将其用作一个。

---

现在，关于您的编辑:堆不必必须按降序排列。最大堆是降序(最大元素在前)，最小堆是升序(最小元素在前)。

标准库中的默认是构建一个最小堆，使用operator<进行比较。要改为构建最大堆，您只需传递 std::greater<int>或任何(可选的)最终参数。