Mam stertę za pomocą std::make_heap:

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

Teraz zaktualizuję stertę, zmieniając jeden losowy element:

v[3] = 35;

Czy istnieje sposób w standardowej bibliotece, aby ponownie dostosować stertę w O(log n), gdzie n jest wielkości pojemnika. Zasadniczo szukam funkcji stertyfikacji. Wiem, jaki element został zmieniony.

Rozumiem, że std::make_heap jest czas O(n log n). Przeszedłem również zduplikowane pytanie, ale różni się w sensie, że zmieniają się maksymalny element. W tym rozwiązaniu jest już podane z złożoności O(log n).

Próbuję zmienić dowolny losowy element w stosie sterty.

5
code707 3 czerwiec 2018, 18:39

4 odpowiedzi

Najlepsza odpowiedź

Możesz to zrobić sam:

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;
}
5
Matt Timmermans 3 czerwiec 2018, 18:44

Jeśli przyjrzymy się bliżej na Twoim oświadczeniu:

Teraz zakłócę stertę przez zmianę jednego Random Element sterty.

W przypadku sterowania w O(log n) możesz bezpośrednio "przeszkadzać" z przodu z przodu z przodu (który odpowiada wkładaniu lub usuwaniu elementu). W takich przypadkach (ponowne) sterowanie można następnie osiągnąć za pomocą {{X1} } i std::pop_heap algorytmy, które zajmują logarytmiczne Czas pracy.

To znaczy, tył:

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

Lub przód:

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)

W przeciwnym razie musisz odtwarzać cały wektor z std::make_heap, który bierze liniowy czas biegania.


Podsumowanie

Nie można zmodyfikować dowolnego elementu sterty i osiągnąć stertę w logarytmicznym czasie pracy ze standardową biblioteką (tj. Szablony funkcji std::push_heap i std::pop_heap). Jednak zawsze możesz wdrożyć operacje pływanie Sypity i>, aby sterować w czasie pracy logarytmicznej.

4
眠りネロク 3 czerwiec 2018, 19:05

Staram się stawić czoła temu problemowi, że chcesz "aktualizować stertę". Jednak w końcu, zamiast kodować niestandardową aktualizowaną stertę lub coś takiego, rozwiązałem go trochę inaczej.

Aby utrzymać dostęp do najlepszego elementu bez konieczności jawnie przejść przez stertę, można użyć wersjonowanych opakowań elementów, które chcesz zamówić. Każdy unikalny, prawdziwy element ma licznik wersji, który jest zwiększony za każdym razem, gdy zostanie zmieniony element. Każdy wrapper wewnątrz sterty przenosi następnie wersję elementu, będąc wersją w momencie utworzenia opakowania:

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

Podczas wykonywania najwyższego elementu z sterty możesz po prostu sprawdzić ten element opakowania, aby sprawdzić, czy jest na bieżąco z oryginałem. Jeśli nie, po prostu usuwaj go i wyskocz ponownie. Ta metoda jest dość wydajna, a ja też widziałem w innych aplikacjach. Jedyną rzeczą, o którą musisz się dbać, jest to, że przechodzisz przez stertę, aby oczyścić go z przestarzałych elementów, od czasu do czasu (powiedzmy, co 1000 wstawień lub tak).

2
volzotan 3 czerwiec 2018, 15:58

Nie jest możliwe modyfikowanie dowolnego elementu sterty w czasie pracy logarytmicznej bez naruszenia właściwości sterty, tylko za pomocą szablonów funkcyjnych std::pop_heap() i std::push_heap(), że standardowa biblioteka zapewnia.

Jednak możesz zdefiniować własny szablon funkcyjny typu STL, set_heap_element(), w tym celu:

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

Następnie możesz dostarczyć następujące uproszczone przeciążenie set_heap_element() dla sterty max :

#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>{});
}

To przeciążenie używa obiektu std::less<T> jako obiekt funkcji porównania dla oryginalnego szablonu funkcji.


Przykład

W przykładzie max-heap set_heap_element() może być używany w następujący sposób:

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

Możesz użyć std::is_heap(), który zajmuje liniowy czas, zawsze, gdy chcesz sprawdzić, czy właściwość max-heap jest nadal spełniona przez v po ustawieniu elementu za pomocą {{x2 }} Szablon funkcji powyżej:

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

A co z min ?

Możesz osiągnąć to samo dla sterty Min , przekazując obiekt std::greater<int> jako ostatni argument funkcji wywołuje do std::make_heap(), set_heap_element() i std::is_heap() }:

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>{}));
1
眠りネロク 6 sierpień 2018, 05:47