删除 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());

是不是'safe'去掉max然后push一个新元素到堆中？我测试了一下，好像是这样的。我有理由不这样做吗？

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

Answer 1

在通过 make_heap, the maximum element will be on the front, and the appropriate way to remove it is with std::pop_heap 创建的最大堆中，句号。

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

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

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

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

Answer 2

您要求的内容与您 post 正文中的链接问题几乎完全相同。

// Precondition is that v is already a heap.
int get_max_element_add_new (std::vector<int> &v, int value) {
    v.push_back(value);
    std::pop_heap(v.begin(), v.end());
    value = v.back();
    v.pop_back();
    return value;
}

由于 pop_heap 将交换第一个值和最后一个值，因此 back 将包含您要删除的最大值。

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

Single 'Heapify' call when removing max and adding a new element c++ std::make_heap

c++

algorithm

heap