数据结构 提取优先级队列的最后一个元素而不进行遍历
简介
C++中的优先级队列与数据结构中的普通队列不同,它有一个区别:它的所有元素都有优先级。我们可以通过在队列中遍历来提取其元素。
但是,在本教程中,我们将尝试一种无需遍历的方法来提取优先级队列的最后一个元素。让我们开始吧…
什么是优先级队列
在数据结构中,抽象的数据类型是优先级队列。它是一个队列,其所有元素都有一些相关的优先级。它的所有元素都根据它们的优先级被删除。优先级较高的数据首先被提取,而优先级较低的数据则被提取。队列数据/元素可以是整数或字符串,但没有NULL值。
如果两个元素有相同的优先级,那么优先级队列将遵循FIFO(先进先出)原则进行提取。
有两种类型的优先级队列可以提取其元素 −
- 升序优先队列 – 在这种类型的优先队列中,元素按升序提取。具有最小优先级的元素将首先被删除。
-
降序优先 级队列 – 在这种类型的优先级队列中,元素以递增的顺序被提取。具有最大优先权的元素将首先被删除。
语法
提取优先级队列的最后一个元素而不需要遍历
这里,我们要提取优先级队列的最后一个元素,而不需要遍历整个队列。我们通过二进制树来实现优先级队列。在这个过程中,我们使用了以下内置的方法
- 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++语言从队列中提取最后一个元素的代码
输出
总结
优先级队列可以通过数组、堆数据结构、关联列表和二叉树来实现。它有助于揭示隐藏的路线和各种算法。
本教程到此结束,我希望你觉得它很有意义。