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

Question

Why is priority_queue implemented using heaps when without using heaps too we can implement it with just vectors.

Suppose we use vector as a queue and keep the elements in decreasing order. We can use this as priority queue.

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

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

For top element: O(1)

In addition, we can have access kth maximum element in just O(1) time which is not the case with heaps.

Then, why do we use heaps for implementing priority queues?

StackOverflow's just posted a blog entry about how the site doesn't seem very welcoming. People's response to this question is like a case in point. @prashantshishodia: I am sorry you have experienced this. — Richard
– Richard, Commented May 3, 2018 at 12:25

Community · Accepted Answer · 2020-06-20 09:12:55Z

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

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

No, you can't. By using a sorted array/vector you can only search for the correct index on O(log N) but to do the actual insert or delete you have to shift other elements which is O(N).

Caleth · Accepted Answer · 2018-05-03 12:22:15Z

The default priority queue does use std::vector. It layers the heap algorithms over that to get the required performance characteristics.

A sketch implementation:

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

Compare with your suggestion

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

I was referencing the first snippet, not the second one. You effectively pop_back(), but the element you pop is actually the element that was at the front() of the vector before pop_heap because pop_heap first swap front() and back(), and then move the old back() at the correct position in the vector.

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Related