使用C ++标准库以对数时间进行堆化 [英] Heapify in logarithmic time using the C++ standard library

问题描述

我有一个堆使用 std :: make_heap ：

std::vector<int> v{1,2,3,5,9,20,3};
std::make_heap(v.begin(), v.end());

现在我通过更改一个随机元素来更新堆：

now I update the heap by changing one random element:

v[3] = 35;

标准库中是否有一种方法可以在 O中再次调整堆（ log n）时间，其中<​​code> n 是容器的大小。基本上我正在寻找堆功能。我知道更改了哪些元素。

Is there a way in standard library in to adjust heap again in O(log n) time where n is size of container. Basically I am looking for heapify function. I know what element has been changed.

我知道 std :: make_heap 是 O（n log n）时间。我也经历了重复的问题，但这在改变最大元素的意义上是不同的。对于该问题，已经给出了 O（log n）复杂度的解决方案。

I understand that std::make_heap is O(n log n) time. I have also gone through duplicate question but that is different in sense that it is changing max element. For that solution is already given of O(log n) complexity in that question.

我正在尝试更改堆中的任何随机元素。

I am trying to change any random element within heap.

推荐答案

您可以自己做：

void modify_heap_element(std::vector<int> &heap, size_t index, int value)
{
    //while value is too large for its position, bubble up
    while(index > 0 && heap[(index-1)>>1] < value)
    {
        size_t parent = (index-1)>>1;
        heap[index]=heap[parent];
        index = parent;
    }
    //while value is too large for its position sift down
    for (;;)
    {
        size_t left=index*2+1;
        size_t right=left+1;
        if (left >= heap.size())
            break;
        size_t bigchild = (right >= heap.size() || heap[right] < heap[left] ?
                           left : right );
        if (!(value < heap[bigchild]))
           break;
        heap[index]=heap[bigchild];
        index = bigchild;
    }
    heap[index] = value;
}

这篇关于使用C ++标准库以对数时间进行堆化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！