数据结构 提取优先级队列的最后一个元素而不进行遍历

数据结构 提取优先级队列的最后一个元素而不进行遍历

简介

C++中的优先级队列与数据结构中的普通队列不同,它有一个区别:它的所有元素都有优先级。我们可以通过在队列中遍历来提取其元素。

但是,在本教程中,我们将尝试一种无需遍历的方法来提取优先级队列的最后一个元素。让我们开始吧…

什么是优先级队列

在数据结构中,抽象的数据类型是优先级队列。它是一个队列,其所有元素都有一些相关的优先级。它的所有元素都根据它们的优先级被删除。优先级较高的数据首先被提取,而优先级较低的数据则被提取。队列数据/元素可以是整数或字符串,但没有NULL值。

如果两个元素有相同的优先级,那么优先级队列将遵循FIFO(先进先出)原则进行提取。

有两种类型的优先级队列可以提取其元素 −

  • 升序优先队列 – 在这种类型的优先队列中,元素按升序提取。具有最小优先级的元素将首先被删除。

  • 降序优先 级队列 – 在这种类型的优先级队列中,元素以递增的顺序被提取。具有最大优先权的元素将首先被删除。

语法

 priority_queue<queue_type> queue_name
Bash

提取优先级队列的最后一个元素而不需要遍历

这里,我们要提取优先级队列的最后一个元素,而不需要遍历整个队列。我们通过二进制树来实现优先级队列。在这个过程中,我们使用了以下内置的方法

  • size() – 它返回优先级队列的大小。

语法 - queue_name.size()

  • insert() – 将 元素 插入 优先级队列中。

语法 – queue_name.insert(data_type)

  • getMin() -它 返回优先级队列中最小的元素。

语法 – queue_name.getMin()

  • getMax() -它 返回优先级队列中最大的元素。

语法 – queue_name.getMax()

  • isEmpty() – 如果队列是空的, 则返回 true。

  • deleteMin() -删除 最小的队列元素。

语法 – queue_name.deleteMin()

  • deleteMax() – 删除最大的队列元素。

语法 – queue_name.deleteMax()

算法

第1步 - 为队列操作创建一个结构类。

第2步 - 创建一个用于自动排序的元素的多集。

第 3 步 - 将元素插入优先队列中。

第 4 步 - 通过使用内置的getMin()和getMax()等函数来获取最小和最大的元素,而无需遍历。

例子

用C++语言从队列中提取最后一个元素的代码

#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;
}
Bash

输出

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

总结

优先级队列可以通过数组、堆数据结构、关联列表和二叉树来实现。它有助于揭示隐藏的路线和各种算法。

本教程到此结束,我希望你觉得它很有意义。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

登录

注册