原文:
是数据结构的扩展，其中每个元素都有一个与之相关联的特定优先级。它基于优先级值，从队列中删除元素。
对优先级队列的操作:
- enqueue(): 该函数用于将新数据插入队列。
- 出列():该函数从队列中移除优先级最高的元素。
- peek()/top(): 此函数用于获取队列中优先级最高的元素，而不将其从队列中移除。
方法:想法是创建一个结构来存储元素的值和优先级，然后创建该结构的数组来存储元素。以下是将要实现的功能:
- enqueue(): 用于在队列末尾插入元素。
- peek():
- 遍历优先级队列，找到优先级最高的元素并返回其索引。
- 在多个元素具有相同优先级的情况下，找到具有最高优先级的具有最高值的元素。
- 出列():
- 使用 peek() 函数找到优先级最高的索引让我们将该位置称为 ind ，然后将位置 ind 之后的所有元素的位置向左移动一个位置。
- 将尺寸减小一。
下面是上述方法的实现:
c
// c program for the above approach
#include
using namespace std;
// structure for the elements in the
// priority queue
struct item {
int value;
int priority;
};
// store the element of a priority queue
item pr[100000];
// pointer to the last index
int size = -1;
// function to insert a new element
// into priority queue
void enqueue(int value, int priority)
{
// increase the size
size ;
// insert the element
pr[size].value = value;
pr[size].priority = priority;
}
// function to check the top element
int peek()
{
int highestpriority = int_min;
int ind = -1;
// check for the element with
// highest priority
for (int i = 0; i <= size; i ) {
// if priority is same choose
// the element with the
// highest value
if (highestpriority
== pr[i].priority
&& ind > -1
&& pr[ind].value
< pr[i].value) {
highestpriority = pr[i].priority;
ind = i;
}
else if (highestpriority
< pr[i].priority) {
highestpriority = pr[i].priority;
ind = i;
}
}
// return position of the element
return ind;
}
// function to remove the element with
// the highest priority
void dequeue()
{
// find the position of the element
// with highest priority
int ind = peek();
// shift the element one index before
// from the position of the element
// with highest priortity is found
for (int i = ind; i < size; i ) {
pr[i] = pr[i 1];
}
// decrease the size of the
// priority queue by one
size--;
}
// driver code
int main()
{
// function call to insert elements
// as per the priority
enqueue(10, 2);
enqueue(14, 4);
enqueue(16, 4);
enqueue(12, 3);
// stores the top element
// at the moment
int ind = peek();
cout << pr[ind].value << endl;
// dequeue the top element
dequeue();
// check the top element
ind = peek();
cout << pr[ind].value << endl;
// dequeue the top element
dequeue();
// check the top element
ind = peek();
cout << pr[ind].value << endl;
return 0;
}
output:
16
12
复杂度分析:
- 入队():o(1)
- peek(): o(n)
- 出列:o(n)
优先队列的应用 :
- 对于，中央处理器必须处理具有优先级的特定任务。具有较高优先级的进程首先被执行。
- 在分时计算机系统中，等待 cpu 时间的过程被加载到中。
- 排序优先级队列用于对进行排序。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
