Работает ли std :: push_heap для сложности O (n) вместо O (logN) в этом случае? - PullRequest
Новая
       71

Работает ли std :: push_heap для сложности O (n) вместо O (logN) в этом случае?

3 голосов
/ 23 октября 2019

Я заменил один случайный элемент кучи и затем вызвал push_heap в этом контейнере. Какую сложность он имеет в этом случае: O (n) или O (logN)? 

/* heap elements are stored on a random-access container */
std::vector<int> Q = { 3, 4, 2, 1 };

/* heapify Q (linear run-time complexity) */
std::make_heap(Q.begin(), Q.end());

std::cout << std::is_heap(Q.begin(), Q.end()) << std::endl;
std::cout << Q[3] << std::endl;
Q[3] = 5;
std::push_heap(Q.begin(), Q.end());
std::cout << std::is_heap(Q.begin(), Q.end()) << std::endl;

Ответы [ 3 ]

3 голосов
/ 23 октября 2019

Вы задаете не тот вопрос. Вместо того, чтобы просить о сложности времени, вы должны спросить, является ли то, что вы делаете, правильно определенным поведением.

Ответ: push_heap имеет предварительное условие, что диапазон, который вы передаете, является допустимой кучей. Точнее, если вы дадите ему диапазон [first, last[, то в качестве кучи потребуется только [first, last-1[, и будет вставлен элемент в last-1. Поэтому, если это предварительное условие не выполняется, поведение не определено (и это имеет место с push_heap, как с любыми другими алгоритмами STL, насколько я знаю). Но если предварительное условие выполнено, вы гарантированно получите O (log N) здесь.

В вашем примере куча все еще действует, потому что вы меняете последний элемент (который не обязательно должен быть частьюкуча), поэтому сложность остается O (log N). Если бы это больше не было кучей, теоретически, все могло бы произойти: Crash, O (n), O (2 ^ n), драконы в носу.

На практике, однако, сложность останется на O (logN) потому что новая запись все равно будет просеиваться при максимальных слоях кучи O (log N), даже если один из них неправильный, и отсеивание останавливается неправильно (на самом деле, если куча неверна в первую очередь, не может быть «правильной»)просеивание).

3 голосов
/ 23 октября 2019

Сложность времени std::push_heap является логарифмической, то есть O (logN):

До логарифмическая на расстоянии междупервый и последний : сравнивает элементы и потенциально меняет их местами (или перемещает) до тех пор, пока не переставит их в более длинную кучу.

где N = std::distance(first, last).

Примечание. В случае вызоваэтот метод в неверной куче , как прокомментировал @interjay, "поведение равно неопределено , и вы не можете знать его сложность илиэффекты ", так как этот метод не реорганизует кучу в допустимую. ref заявляет:

Учитывая кучу в диапазоне [first, last-1), эта функция расширяет диапазон, который считается кучей, до [first, последний), поместив значение в (last-1) в соответствующее ему местоположение внутри него.

Итак, если бы я на самом деле делал это, я бы не беспокоился о сложности времени, нодля непредсказуемого поведения.

Чтобы продемонстрировать это поведение, попробуйте изменить 2-й элемент (любой, кроме последнего, как прокомментировал @ThomasSablik - потому что если вы измените Q.back(), куча будет действительной после std::push_heap(Q.begin(), Q.end());), и вы заметите, что куча остается недействительной после вызова std::push_heap - вам нужно вызвать линейный (по сложности) метод std::make_heap, чтобы реорганизовать вашу теперь недействительную кучу.

1 голос
/ 23 октября 2019

Сложность push_heap не меняется, но она четко определена, если вы измените последний элемент.

Если вы измените Q.back(), куча будет действительна после std::push_heap(Q.begin(), Q.end());. Если вы измените элемент, отличный от Q.back(), поведение не будет определено. Куча может стать недействительной. Сложность O (log N) в любом случае.

Если вам нужно изменить случайный элемент, вызовите make_heap вместо push_heap со сложностью O (N) или используйте пользовательскую функцию, например: 

#include <algorithm>
#include <iostream>
#include <vector>

using Container = std::vector<int>;

void push_heap(Container &Q, Container::size_type index, Container::value_type value) {
    Q[index] = value;
    for (Container::size_type i{index + 1}; i > 1; i /= 2) {
        if (Q[i - 1] <= Q[i/2 - 1]) break;
        std::swap(Q[i - 1], Q[i/2 - 1]);
    }
}

int main() {
    Container Q = { 1, 2, 4, 8, 16, 32 };

    std::make_heap(Q.begin(), Q.end());

    std::cout << std::boolalpha << std::is_heap(Q.begin(), Q.end()) << '\n';
    for (const auto &el : Q) {
        std::cout << el << ' ';
    }
    std::cout << '\n';
    push_heap(Q, 4, 20);
    // Q[4] = 20;
    // std::push_heap(Q.begin(), Q.end());
    std::cout << std::is_heap(Q.begin(), Q.end()) << '\n';
    for (const auto &el : Q) {
        std::cout << el << ' ';
    }
}

Эта функция устанавливает элементкучи и сохраняет свойство кучи в O (log N).

Вывод: 

true
32 16 4 8 2 1 
true
32 20 4 8 16 1

В примере элемент Q[4] имеет значение 20. Поведение push_heapне определен для этого случая. Обычный результат - неверная куча. Как вы можете видеть, пользовательская функция push_heap реорганизует кучу в итерациях журнала (N) и возвращает действительную кучу.

...