Priority Queues
Description
Priority queues are abstract data structures that provide efficient access to the element with the highest (or lowest) priority. They are typically implemented using heaps, allowing for efficient insertion, deletion of the highest priority element, and peek operations in O(log n) time complexity.
C++ Code
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
pq.push(5);
cout << "Top element: " << pq.top() << "\n";
pq.pop();
cout << "Top element after pop: " << pq.top() << "\n";
return 0;
}
Time and Space Complexity
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insertion (push) | O(log n) | O(n) |
| Deletion (pop) | O(log n) | O(n) |
| Peek (top) | O(1) | O(1) |
Where:
- n: Number of elements in the priority queue.