Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Solution Approach
2.1.
C++ Code
2.2.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is a priority queue?
3.2.
What is a multiset and how it is implemented? What is the time taken for insertion/deletion in a multiset? 
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Double Ended Priority Queue

Author Ayush Prakash
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Heap and Priority Queue

Introduction 

Let us first discuss the problem statement. The problem statement goes like this: We need to implement a data structure known as the double-ended priority queue which supports the following methods: 

  1. add(int x): Insert an element with the value ‘X’ into the double-ended priority queue. 
  2. printQueue(): Outputs the content of the double-ended priority queue. 
  3. getMax(): Outputs the maximum element from the double-ended priority queue. 
  4. getMin(): Outputs the minimum element from the double-ended priority queue.
  5. eraseMax(): Removes the maximum element from the double-ended priority queue.
  6. eraseMin(): Removes the minimum element from the double-ended priority queue. 
  7. isEmpty(): Outputs a boolean, true when the double-ended priority queue is empty and false otherwise. 
  8. size(): Outputs the number of elements in the double-ended priority queue.

Note: in this blog “queue” and “double-ended priority queue” are used interchangeably. 

See, Priority Queue using C++

Solution Approach

  • We will use a multiset as our main data structure and build our queue on top of it. Let us define a multiset:  A multiset is a container that is similar to a set but it can hold multiple elements of the same values. 
  • It is internally implemented as a self-balancing binary search tree. This makes insertion and deletion time in a multiset O(logn). 
  • Accessing elements in a multiset using iterators will take O(1) time. 
  • Below is the implementation, we have used the inbuilt methods of multiset to achieve what the problem statement demands.

C++ Code

#include <bits/stdc++.h>
using namespace std;

class DoubleEndedPQ
{
private:
  multiset<int> nums;

public:

  // Constructor clears the multiset 'nums'
  DoubleEndedPQ()
  {
      nums.clear();
  }

  // This method inserts an element 'x' into the queue
  void add(int x)
  {
      nums.insert(x);
  }

  // This method prints the content of the queue
  void printQueue()
  {
      for (auto it = nums.begin(); it != nums.end(); it++)
      {
          cout << *it << " ";
      }
      cout << endl;
  }

  // This method gets the maximum element from the queue
  int getMax()
  {
      if (nums.size() == 0)
      {
          return INT_MAX;
      }
      return *nums.rbegin();
  }

  // This method gets the minimum element from the queue
  int getMin()
  {
      if (nums.size() == 0)
      {
        return INT_MAX;
      }
      return *nums.begin();
  }

  // This method removes the largest element from the queue
  void eraseMax()
  {
      if (nums.size() != 0)
      {          
        nums.erase(*nums.rbegin());
      }
      else
      {
          cout << "No elements found." << endl;
      }
  }

// This method removes the smallest element from the queue
  void eraseMin()
  {
      if (nums.size() != 0)
      {
          nums.erase(*nums.begin());
      }
      else
      {
          cout << "No elements found." << endl;
      }
  }
 
// Checks if the queue is empty
  bool isEmpty()
  {
      return nums.size() == 0 ? true : false;
  }

 // This methods returns the size of the queue
  int size()
  {
    return nums.size();
  }
};

int main()
{
  DoubleEndedPQ depq = DoubleEndedPQ();

  // Adding elements to the queue
  depq.add(1);
  depq.add(3);
  depq.add(3);
  depq.add(4);
  depq.add(5);
  depq.add(2);

  // Printing the contents of the queue
  cout << "Elements in the queue: ";
  depq.printQueue();

  // Getting the maximum element
  cout << "Maximum element: " << depq.getMax() << endl;

  // Getting the minimum element
  cout << "Minimum element: " << depq.getMin() << endl;

  // Removing the maximum element
  depq.eraseMax();
  cout << "After removing the largest element: ";
  depq.printQueue();

  // Removing the minimum element
  depq.eraseMin();
  cout << "After removing the smallest element: ";
  depq.printQueue();

  // Checking if the queue is empty
  cout << depq.isEmpty() << endl;

  // getting the size of the queue
  cout << depq.size() << endl;
}

Output:

output

Complexity Analysis

Time complexity

  1. add(int x) / removeMax() / removeMin() : O(logN), we are inserting / deleting an element, and insertion / deletion time in a multiset is O(logN) as it uses self-balancing BST in the background (as discussed above). 
  2. printQueue(): O(N), as we need to traverse through the queue to print the elements.
  3. getMin() / getMax(): O(1) as we are accessing the required elements using iterator. 
  4. isEmpty(): O(1)
  5. size(): O(1)


Space complexity

O(N), as we are using an auxiliary container (multiset) to store all the ‘N’ elements. 

Also Read, Prefix Sum Array

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a priority queue?

It is similar to a queue but the elements are ordered based on priority. For example, in the min priority queue, the minimum element is dequeued first followed by the second minimum, third minimum, and so on. Whereas in the case of a max priority queue, the maximum element is dequeued first. Internally, priority queues are implemented using a heap data structure.  

What is a multiset and how it is implemented? What is the time taken for insertion/deletion in a multiset? 

A multiset is a container similar to a set, but it can hold multiple elements with the same value. It is implemented using a self-balancing binary tree. The time taken for insertion/deletion operation is O(logN), where “N” is the number of elements in the multiset.

Conclusion

  1. We implemented a “double-ended priority queue” using multisets in C++ from scratch.  
  2. We discussed that a multiset is implemented using a self-balancing binary search tree and the time is taken for insertion/deletion operation is O(logN) since the height of a self-balancing binary tree is logN.
  3. We also discussed the basics of the priority queue and heap data structure


Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Priority Queue using Java
Next article
Binary Heap
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass