当我们可以更有效地使用向量来实现优先级队列时，为什么要使用堆来实现它

Question

为什么 priority_queue 使用堆实现而不使用堆我们也可以只使用向量来实现它。

假设我们使用vector作为一个队列，并且让元素降序排列。我们可以将其用作优先队列。

对于插入：我们可以使用二分查找。 Complexity O(logN)

对于删除：这里也可以使用二分查找。 Complexity O(logN)

对于顶部元素：O(1)

此外，我们可以在 O(1) 时间内访问第 k 个最大元素，而堆则不是这种情况。

那么，为什么要用堆来实现优先队列呢？

Answer 1

For insertion : We can use binary search . Complexity O(logN)

For deltion : Here also we can use binary search. Complexity O(logN)

不，你不能。通过使用排序的 array/vector，您只能在 O(log N) 上搜索正确的索引，但要进行实际的插入或删除，您必须移动其他元素，即 O(N).

Answer 2

默认优先级队列确实使用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)
    }
}

当我们可以更有效地使用向量来实现优先级队列时，为什么要使用堆来实现它

Why priority queue is implemented using heaps when we can implement it using just vector more efficiently

c++

implementation

stl

priority-queue