使用STL堆实现O(logn)时间复杂度下的“减小关键字（Decrease Key）”操作

Question

目前STL堆不支持降低关键字的操作，但可以直接更改向量上的值，并再次调用make_heap函数，这需要O(n)的时间。但是这不如使用二叉堆的降低关键字操作高效，后者只需O(logn)的时间。

是否有一种方法可以使用STL堆函数实现O(logn)的时间复杂度呢？

- Jake

Answer 1

我相信没有符合标准的方法来实现这个 - 维基百科也这么说:

没有标准支持减少/增加键操作

尽管它指向了gheap库，这可能值得一看。

问题在于标准没有规定堆结构的形式，也没有规定如何执行操作。(总的来说这是一件好事。)

如果实现正在使用标准二叉堆，那么我认为您可以简单地减少heap[i]处的元素，然后调用push_heap(heap.begin(), heap.begin() + i + 1)，这将执行必要的上堆操作。最终出现在位置i的元素必须比原来那里的值小，因此整个堆的堆属性得以保留。但即使在某些实现中有时候可以工作，这也不被标准支持。

- Alan Stokes

---

还有一个增加关键字的操作呢？你能使用 std 的堆操作来实现它吗？（假设我在 vector 上使用二叉堆） - Gonzalo Solera

@Gonzalo 这似乎应该是一个新问题。 - Alan Stokes

你如何找到正确的 i，即实际实体的堆位置，其键应该减少？ - m8mble

Answer 2

你可以使用 pop_heap，然后递减值，接着使用 push_heap：

int main() {
    //Create the heap
    std::vector<int> heap{1,2,3,4,5,6,7};
    std::make_heap(heap.begin(), heap.end());

    //Decrease key
    std::pop_heap(heap.begin(), heap.end());
    --*(std::prev(heap.end()));
    std::push_heap(heap.begin(), heap.end());
}

编辑：这是您的意思吗？还是您想要能够降低堆中任何元素的键值？

- Mankarse