代码之家 › 专栏 › 技术社区 › cjlovering

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

heap algorithm c++

cjlovering · 技术社区 · 7 年前

    // 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());

删除max并将新元素推到堆中是否“安全”?我已经测试过了,似乎是这样。有什么理由我不应该这样做吗?

2 回复 | 直到 7 年前

AndyG 7 年前

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

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

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

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

jxh 6 年前

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

推荐文章

NOBUD · 最大堆插入函数实现C++

2 年前

JimBelushi2 · 合并排序创建内存堆

6 年前

Arda Ä°brahim Gökçe · 在遍历最小堆时获取垃圾值

6 年前

bordus · 将“人员”分成两个大小相等的团队,以达到最大的总体效率

6 年前

Alexy Grabov · 查找最大堆中k个最大元素的位置

6 年前

James · 最大节点堆java

6 年前

Rodolphe Lemasquerier · 在python中使用heapq获取优先级列表的问题

6 年前

Maxxx · 使用堆在O(N log K)时间内查找前K个元素

6 年前

Karthik · 限制Go堆接口实现的优先级队列的大小

6 年前

mourinho · 使用数组实现最小堆[关闭]

6 年前