删除max并添加新元素c++std::make\u heap时单个“Heapify”调用

在通过创建的最大堆中 make_heap ,最大元素将位于正面,适当的移除方法是使用 std::pop_heap 时期

A. pop_front (不是 pop_back 就像你假设的那样)确实会从堆中删除最大元素,但你不再保证有一个堆。也就是说,弹出第一个元素可以有效地移动堆 左边 正当 child越大,则heap属性就会丢失(即使它对第一组子级有效,也可能由于数组中的移位而使任何子树无效)。

此外,如果您使用的是连续容器,如 std::vector ,然后是 pop_正面 std::vector::erase 在…上 vector::begin pop_heap .

您可能(过早)优化的一个场景是,如果您只是想 具有另一个元素的最大元素至少与现有最大元素一样大,否则,>=到最大元素的最大子元素。在这种情况下,可能会达到O(1)复杂度,但在一般情况下不太可能。

// 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 将包含要删除的最大值。