c++ - 在最小堆中查找最大元素

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()指向的那个元素)显然是一个叶节点，它的父元素是最后一个非叶子节点，因为如果在该叶子节点之后有一个非叶子节点，则我们假定该元素为堆的最后一个元素不是最后一个元素，这是一个矛盾。

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

您可以轻松地找到最后一个节点的父节点在哪里:给定i作为堆元素的索引，其父节点位于索引(i-1)/ 2。因此，最后一个非叶子节点的索引为 (h.size() - 2) / 2，因此第一个叶子节点的索引为 (h.size() - 2) / 2 + 1。

X假设最小堆中的最大元素位于非叶子节点中。这意味着它至少具有一个子节点。由于 min-heap property，此子节点必须大于或等于其父节点。如果子节点大于其父节点(这是最大元素)，则子节点大于最大节点。这是不可能的，因为我们有矛盾。因此，其所有子节点也必须为最大值，以此类推。因此，如果在堆中重复最大值或唯一的最大值必须与叶节点相对应，则最终在叶节点之一中存在最大值。