优先级队列|集合 1(简介)
原文:https://www . geesforgeks . org/priority-queue-set-1-introduction/
优先级队列是队列的扩展,具有以下属性。
- 每个项目都有一个相关的优先级。
- 优先级高的元素在优先级低的元素之前出队。
- 如果两个元素具有相同的优先级,则根据它们在队列中的顺序提供服务。
在下面的优先级队列中,具有最大 ASCII 值的元素将具有最高优先级。
典型的优先级队列支持以下操作。 插入(项目,优先级):插入具有给定优先级的项目。 获取最高优先级():返回最高优先级的项目。 删除最高优先级():删除最高优先级的项目。
如何实现优先级排队? *使用数组:* 一个简单的实现就是使用数组的如下结构。
struct item {
int item;
int priority;
}
insert()操作可以通过在 O(1)时间内在数组末尾添加一个项来实现。
getHighestPriority()操作可以通过线性搜索数组中优先级最高的项来实现。这个操作需要 O(n)个时间。
deleteHighestPriority()操作可以通过首先线性搜索一个项目,然后通过将所有后续项目向后移动一个位置来移除该项目来实现。
我们也可以使用链表,链表所有操作的时间复杂度和数组一样。链表的优点是 deleteHighestPriority()可以更有效,因为我们不必移动项目。
使用堆: 堆通常是优先队列实现的首选,因为堆比数组或链表提供更好的性能。在二进制堆中,getHighestPriority()可以在 O(1)时间实现,insert()可以在 O(Logn)时间实现,deleteHighestPriority()也可以在 O(Logn)时间实现。 借助斐波那契堆,insert()和 getHighestPriority()可以在 O(1)摊销时间内实现,deleteHighestPriority()可以在 O(Logn)摊销时间内实现。
优先级队列的应用: 1) CPU 调度 2)像迪克斯特拉最短路径算法Prim 最小生成树等图形算法 3)所有涉及优先级的队列应用。
优先级队列是使用堆实现的。关于我们自己的实现和库实现,请参考下面的文章。
有用链接:
参考文献: http://en.wikipedia.org/wiki/Priority_queue
如果你发现任何不正确的地方,或者你想分享更多关于上面讨论的话题的信息,请写评论。
版权属于:月萌API www.moonapi.com,转载请注明出处