Extract the last element of the priority queue without traversing

Introduction

The priority queue in C is different from the ordinary queue in the data structure. It has one difference: all elements have priority. We can extract its elements by iterating over the queue.

However, in this tutorial, we are trying a way to extract the last element of the priority queue without traversing. let's start……

What is a priority queue?

In the data structure, the abstract data type is the priority queue. It is a queue where all elements have some associated priority. All its elements are removed according to their priority. Data with higher priority is extracted first, data with lower priority is extracted first. Queue data/elements can be integers or strings, but cannot be NULL values.

If two elements have the same priority, the priority queue will be fetched according to the FIFO (first in, first out) principle.

There are two types of priority queues whose elements can be extracted -

• Ascending Priority Queue − In this type of priority queue, elements are fetched in ascending order. Elements with the lowest priority will be removed first.

• Descending Priority Queue − In this type of priority queue, elements are fetched in ascending order. Elements with the highest priority will be removed first.

grammar

 priority_queue<queue_type> queue_name

Do not traverse the last element of the extraction priority queue

Here, we extract the last element of the priority queue without traversing the entire queue. We implement priority queues through binary trees. Use the following built-in methods during this process -

• size() - It returns the size of the priority queue.

  Syntax− queue_name .size()

• insert() - Inserts an element into the priority queue.

  Syntax−queue_name.insert(data_type)

• getMin() - It returns the minimum element of the priority queue.

  Syntax−queue_name.getMin()

• getMax() −It ​​returns the largest element in the priority queue.

  Syntax − queue_name.getMax()

The Chinese translation is:

Syntax − queue_name.getMax()

• isEmpty() −Returns true if the queue is empty.

• deleteMin() −Delete the smallest queue element.

  Syntax−queue_name.deleteMin()

• deleteMax() - Delete the largest queue element

  Syntax−queue_name.deleteMax()

algorithm

Step 1 − Create a structure class for queue operations.

Step 2 − Create a multiset to automatically sort elements.

Step 3 − Insert the element into the priority queue.

Step 4 − By using built-in functions such as getMin() and getMax, you can get the minimum and maximum elements () without traversing.

Example

C code to extract the last element from the queue

#include <bits/stdc++.h>
using namespace std;
  
// declaring a struct class for the Priority Queue
struct PQ  {
   multiset<int> s;
   
   //Getting the size of the Queue
   int size() { 
      return s.size(); 
   }
   
   //Checking Queue is empty or not
   bool isEmpty() { 
      return (s.size() == 0); 
   }
   
   void insert(int i) { 
      s.insert(i); 
   }
  
   //Method to get the smallest element of the Queue
   int getMin() { 
      return *(s.begin()); 
   }
   
   // Method to get the largest Queue element
   int getMax() { 
      return *(s.rbegin()); 
   }
   
   // Deleting Queue elements
   void deleteMin() {
      if (s.size() == 0)
         return;
      
      auto i = s.begin();
      s.erase(i);
   }
      
   // Method to delete the largest element
   void deleteMax() {
      if (s.size() == 0)
      return;
      
      auto i = s.end();
      i--;
      s.erase(i);
   }
};
  
//Main code
int main() {
   PQ p;   //initializing the Priority Queue
   
//inserting Queue elements
   p.insert(20);      
   p.insert(30);
   p.insert(50);
   p.insert(60);
   p.insert(90);
   
   cout << "Smallest Element is: " << p.getMin() << endl;
   cout << "Largest Element is: " << p.getMax() << endl;
   
   p.deleteMin();
   cout << "Smallest Element is: " << p.getMin() << endl;
   
   p.deleteMax();
   cout << "Largest Element is: " << p.getMax() << endl;
   
   cout << "Size of the Queue is: " << p.size() << endl;
   
   cout << "Queue is empty?: "
   << (p.isEmpty() ? "YES" : "NO") << endl;
   
   return 0;
}

Output

Smallest Element is: 20
Largest Element is: 90
Smallest Element is: 30
Largest Element is: 50
Queue is Empty?: NO

in conclusion

Priority queues can be implemented through arrays, heap data structures, linked lists and binary trees. It helps expose hidden paths and various algorithms.

This concludes this tutorial, I hope you find it meaningful.

The above is the detailed content of Extract the last element of the priority queue without traversing. For more information, please follow other related articles on the PHP Chinese website!