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

是否可以弹出最大值，推送一个新元素，然后调用push_heap，维护堆并仅调用一次bubble down算法？

    // 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?

最佳答案

在通过 make_heap 创建的最大堆中，最大元素将在最前面，而删除它的适当方法是使用 std::pop_heap (period)。
pop_front(而不是像您一样的pop_back)确实会从堆中删除最大元素，但是不再保证您拥有堆。也就是说，弹出第一个元素会有效地将左子堆移到根中。如果合适的子项更大，则将丢失heap属性(即使它适用于第一组子项，由于数组的移位，它可能会使任何子树无效)。

另外，如果您使用的是诸如std::vector的连续容器，那么pop_front(在 std::vector::erase 上调用 vector::begin )会不幸地浪费您O(N)的时间，这比pop_heap的O(log N)复杂度要差得多。

您可以(过早)进行优化的一种情况是，如果您只是想将最大元素与另一个与现有最大元素大小一样大的元素交换，或者如果失败，则大于等于最大元素的最大子元素。在那种情况下，您可能会达到O(1)的复杂度，但这在一般情况下是不太可能的。

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