c++ - 修改最小堆中的元素并在亚线性时间内重建堆

Question

假设我建立了一个最小堆：

std::vector<int> h;
...
std::make_heap(h.begin(), h.end(), std::greater<int>());

然后我修改一个任意堆元素：

h[7] = 0;

在此修改后，堆属性随后被破坏，因此我不能依赖std::heap_push或std::heap_pop不再依赖。

我知道我可以再次使用std::make_heaponh来重建堆，但这需要线性时间。

有没有办法修改最小堆的元素并在亚线性时间内重建堆？

标签： c++algorithmheapmin-heap