使用C ++标准库以对数时间进行堆化

小编典典

使用C ++标准库以对数时间进行堆化

algorithm

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

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

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

v[3] = 35;

标准库中是否有一种方法可以及时调整容器大小O(log n)所在的堆n。基本上我正在寻找堆功能。我知道哪些元素已更改。

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

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

阅读 287

2020-07-28

共1个答案

小编典典

您可以自己做：

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;
}

2020-07-28