c++ - 删除 max 并添加新元素时的单个 'Heapify' 调用 c++ std::make_heap

Question

是否可以弹出 max，压入一个新元素，然后调用 push_heap，维护堆并且只调用一次向下冒泡算法？

    // What I think is correct:
    heap.push_back(new_element);
    std::push_heap(heap.begin(), heap.end());
    std::pop_heap(heap.begin(), heap.end());
    heap.pop_back();

    // What I hope is correct:
    heap.pop_back();        
    heap.push_back(new_element);
    std::push_heap(heap.begin(), heap.end());

删除最大值并将新元素插入堆是否“安全”？我测试了一下，好像是这样的。我有理由不这样做吗？

非常相关的问题: How to change max element in a heap in C++ standard library?

Answer 1

在通过 make_heap 创建的最大堆中, 最大元素将在前面，删除它的适当方法是使用 std::pop_heap , 时期。

pop_front(不是像您假设的那样 pop_back)确实会从堆中移除最大元素，但您不再保证有堆。也就是说，弹出第一个元素有效地将堆 left 子元素移动到根元素中。如果正确的 child 更大，那么堆属性就会丢失(即使它对第一组 child 有效，它也可能由于数组的移动而使任何子树无效)。

此外，如果您正在使用像 std::vector 这样的连续容器，那么 pop_front(在 std::vector::erase 上调用 vector::begin)就会不幸花费你 O(N) 的时间，这比 pop_heap 的 O(log N) 复杂度要差得多。

您可能(过早地)优化的一种情况是，如果您只是想用至少与现有最大元素一样大的另一个元素交换最大元素，或者失败， >= 到最大元素的最大子元素。在那种情况下，您可能会达到 O(1) 的复杂度，但在一般情况下这不太可能。

最好只有两个 O(log N) 操作。函数增长如此缓慢，以至于 1000 和 100 万元素堆之间几乎没有区别。