Почему приоритетная очередь реализована с использованием кучи, когда мы можем реализовать ее более эффективно, используя только вектор - PullRequest
Новая
       19

Почему приоритетная очередь реализована с использованием кучи, когда мы можем реализовать ее более эффективно, используя только вектор

0 голосов
/ 03 мая 2018

Почему priority_queue реализовано с использованием куч, тогда как без использования куч тоже можно реализовать с помощью только векторов.

Предположим, мы используем вектор как очередь и сохраняем элементы в порядке убывания. Мы можем использовать это как приоритетную очередь.

Для вставки: мы можем использовать бинарный поиск. Complexity O(logN)

Для удаления: Здесь также мы можем использовать бинарный поиск. Complexity O(logN)

Для верхнего элемента: O(1)

Кроме того, мы можем получить доступ к элементу k-го максимума всего за O(1) время, что не относится к кучам.

Тогда, почему мы используем кучи для реализации приоритетных очередей?

Ответы [ 2 ]

0 голосов
/ 03 мая 2018

Очередь приоритетов по умолчанию использует std::vector. Он накладывает алгоритмы кучи поверх этого, чтобы получить требуемые характеристики производительности.

Эскиз реализации: 

template <typename T>
class priority_queue
{
    std::vector<T> elems;
public:
    std::vector<T>::const_reference top() const { 
         return elems.front(); // O(1)
    }
    void push( const T& value ) { 
         elems.push_back(value); // Amortized O(1)
         std::push_heap(elems.begin(), elems.end()); // O(logN)
    }
    void pop() {
         std::pop_heap(elems.begin(), elems.end());  // O(logN)
         elems.pop_back(); // O(1)
    }
}

Сравните с вашим предложением 

template <typename T>
class priority_queue
{
    std::vector<T> elems;
public:
    std::vector<T>::const_reference top() const { 
         return elems.back(); // O(1)
    }
    void push( const T& value ) { 
         std::vector<T>::iterator pos = std::lower_bound(elems.begin(), elems.end(), std::greater<>{}); // O(logN)
         elems.insert(pos, value); // O(N)
    }
    void pop() {
         elems.pop_back(); // O(1)
    }
}
0 голосов
/ 03 мая 2018

Для вставки: мы можем использовать бинарный поиск. Сложность O (logN) * ​​1002 *

Для деления: Здесь также мы можем использовать бинарный поиск. Сложность O (logN) * ​​1004 *

Нет, ты не можешь. Используя отсортированный массив / вектор, вы можете только искать правильный индекс на O(log N), но для фактической вставки или удаления вам нужно сдвинуть другие элементы, которые O(N).

...