在最小堆中查找最大元素

Question

我有一个最小堆：

std::vector<int> h;
...
std::make_heap(h.begin(), h.end(), std::greater<int>());

最小堆操作 std::push_heap 和 std::pop_heap 是我在大多数情况下所需要的，但在极少数情况下，我需要在最小堆中找到最大元素。我可以用 std::max_element:

std::max_element(h.begin(), h.end());

但是，这必须扫描所有的堆元素。

标准库是否提供更有效的算法来查找最小堆中的最大元素？

Answer 1

TL;DR 在最小堆中，最大元素在叶节点^X。因此，您可以将搜索限制在堆的大约一半元素上，即，将最大元素的搜索限制为仅叶节点：

auto max_it = std::max_element(first_leaf_it, h.end());

请注意，这仍然需要线性时间，但常数因子比扫描所有元素要低，大约一半。

以下是由迭代器对提供的用于查找最小堆中最大元素的类 STL 算法实现：

template<typename RandomIt>
auto min_heap_max_element(RandomIt first, RandomIt last) {
   auto n = last - first;

   if (n < 2)
      return first;

   auto first_leaf_it = first + (n - 2) / 2 + 1;
   return std::max_element(first_leaf_it, last);
}

要在您的示例中使用它：

auto max_it = min_heap_max_element(h.begin(), h.end());

如何在堆

中找到第一个叶节点

堆的最后一个元素——h.end()指向的那个——显然是一个叶节点，它的父节点是最后一个非-leaf node 因为如果这个节点后面有一个非叶子节点，我们假设是堆的最后一个元素的元素就不会是最后一个元素，这是矛盾的。

因此，第一个叶节点 将是紧跟在最后一个节点的父节点之后的元素。

你可以很容易地找出最后一个节点的父节点在哪里：给定i一个堆元素的索引，它的父节点在索引(i - 1) / 2 。因此，最后一个非叶节点的索引是 (h.size() - 2) / 2，因此第一个叶节点的索引是 (h.size() - 2) / 2 + 1.

^X 假设 min-heap 中的 maximum element 位于取而代之的是 非叶节点 。这意味着它至少有一个子节点。由于 min-heap property，此子节点必须大于或等于其父节点。如果子节点大于其父节点（即最大元素），则子节点大于最大值。这是不可能的，因为我们有矛盾。因此，它的所有子节点也必须是最大值，对于这些子节点也是如此。所以，最终，如果最大值在堆中重复，或者唯一的最大值必须对应一个叶节点，则最大值位于其中一个叶节点。

Answer 2

如果您确实需要更好的（即次线性）时间复杂度，请考虑使用 Min-max heap。此树中的任何节点都遵循以下属性:

当一个值处于偶数水平时，它是其后代中最大。
当一个值处于奇数水平时，它是其后代中的最少。

因此根节点的值最小，其两个子节点之一的值最大。

insert/extract 操作的时间复杂度与最小堆相同。

检查是否有 C++ MinMax 堆实现？

在最小堆中查找最大元素

Finding max element in min heap

c++

algorithm

heap

optimization

stl

如何在堆