使用C++标准库对对数时间进行加密

你可以自己做:

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

如果我们仔细看一下你的陈述:

现在我换一个来扰乱堆 随机的 堆的元素。

为了治疗 O(log n) 你只能直接“打扰” 后面 或 前面 向量的(以某种方式对应于插入或删除元素)。在这些情况下,可以通过 std::push_heap 和 std::pop_heap 算法,需要对数运行时间。

也就是说,后面:

v.back() = 35;
std::push_heap(v.begin(), v.end()); // heapify in O(log n)

或者前面:

v.front() = 35;

// places the front at the back
std::pop_heap(v.begin(), v.end()); // O(log n)
// v.back() is now 35, but it does not belong to the heap anymore

// make the back belong to the heap again
std::push_heap(v.begin(), v.end()); // O(log n)

否则你需要用 std::make_heap ,这需要线性运行时间。

摘要

使用标准库(即函数模板)不可能修改堆的任意元素并在对数运行时间内实现堆化。 性传播疾病: 和 STD:POPUH堆 )。但是,您始终可以实现堆的 游泳 和 下沉 为在对数运行时间内修复而自行操作。

我也一直面临着需要一个“可更新堆”的问题。但是,最后,我没有编写自定义可更新堆之类的代码,而是用了一点不同的方法解决了这个问题。

为了在不需要显式遍历堆的情况下保持对最佳元素的访问,可以使用要排序的元素的版本化包装器。每个唯一的true元素都有一个版本计数器,每次更改元素时都会增加这个计数器。然后堆中的每个包装都携带元素的一个版本,即创建包装时的版本:

struct HeapElemWrapper
{
    HeapElem * e;

    size_t version;        
    double priority;

    HeapElemWrapper(HeapElem * elem)
     : e(elem), version(elem->currentVersion), priority(0.0)
    {}

    bool upToDate() const
    {
        return version == e->currentVersion;
    }

    // operator for ordering with heap / priority queue:
    // smaller error -> higher priority
    bool operator<(const HeapElemWrapper & other) const
    {
        return this->priority> other.priority;
    }
};

当从堆中弹出最上面的元素时,您可以简单地检查这个包装器元素,看看它是否与原始元素最新。如果不是,简单地处理它,弹出下一个。这种方法非常有效,我在其他应用程序中也看到过。唯一需要注意的是,您要不时地对堆进行一次传递,以清除过时元素(例如,每1000次插入大约一次)。

It's not possible 仅使用函数模板在对数运行时间内修改堆的任意元素而不违反堆属性 std::pop_heap() 和 std::push_heap() 标准库提供的。

但是,您可以定义自己的类似stl的函数模板, set_heap_element() ,为此目的:

template<typename RandomIt, typename T, typename Cmp>
void set_heap_element(RandomIt first, RandomIt last, RandomIt pos, T value, Cmp cmp)
{
    const auto n = last - first;
    *pos = std::move(value); // replace previous value

    auto i = pos - first;
    using std::swap;

    // percolate up
    while (i > 0) { // non-root node
        auto parent_it = first + (i-1)/2;

        if (cmp(*pos, *parent_it))
            break; // parent node satisfies the heap-property 

        swap(*pos, *parent_it); // swap with parent
        pos = parent_it;
        i = pos - first;
    }

    // percolate down
    while (2*i + 1 < n) { // non-leaf node, since it has a left child
        const auto lidx = 2*i + 1, ridx = 2*i + 2;

        auto lchild_it = first + lidx; 
        auto rchild_it = ridx < n? first + ridx: last;

        auto it = pos;
        if (cmp(*it, *lchild_it))
            it = lchild_it;
        if (rchild_it != last && cmp(*it, *rchild_it))
            it = rchild_it;

        if (pos == it)
            break; // node satisfies the heap-property

        swap(*pos, *it); // swap with child
        pos = it;
        i = pos - first;
    }
}

然后,您可以提供以下简化的重载 设置堆元素() 对于一个 最大堆 :

#include <functional> // std::less

template<typename RandomIt, typename T>
void set_heap_element(RandomIt first, RandomIt last, RandomIt pos, T value) {
    return set_heap_element(first, last, pos, value, std::less<T>{});
}

此重载使用 std::less<T> 对象作为原始函数模板的比较函数对象。

例子

在你的 最大值堆 例子, 设置堆元素() 可使用如下:

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

// set 4th element to 35 in O(log n)
set_heap_element(v.begin(), v.end(), v.begin() + 3, 35);

你可以用 std::is_heap() ,这需要线性时间,只要您想检查 最大堆属性 仍然满足于 v 在使用 设置堆元素() 上面的函数模板:

assert(std::is_heap(v.begin(), v.end())); 

那怎么办 闽 堆?

你也可以通过 小顶堆 通过一个 std::greater<int> 对象作为函数调用的最后一个参数 std::make_heap() , 设置堆元素() 和 STD::iSHeHeP() :

std::vector<int> v{1,2,3,5,9,20,3};
// create a min heap
std::make_heap(v.begin(), v.end(), std::greater<int>{});

// set 4th element to 35 in O(log n)
set_heap_element(v.begin(), v.end(), v.begin() + 3, 35, std::greater<int>{});

// is the min-heap property satisfied?
assert(std::is_heap(v.begin(), v.end(), std::greater<int>{}));