原文:
优先级队列是抽象的数据结构，其中队列中的每个数据/值都有特定的优先级。例如，在航空公司，标题为“商务”或“头等舱”的行李比其他行李更早到达。 优先级队列是队列的扩展，具有以下属性。 1)优先级高的元素在优先级低的元素之前出列。 2)如果两个元素具有相同的优先级，则根据它们在队列中的顺序进行服务。 计算机科学中优先级队列的各种应用有: 作业调度算法、中央处理器和磁盘调度、管理不同进程间共享的资源等。
优先级队列和队列的主要区别: 1)在队列中，最早的元素先出队。而在优先级队列中，基于最高优先级的元素被出列。 2)当元素从优先级队列中弹出时，得到的结果或者按递增顺序排序，或者按递减顺序排序。而当元素从一个简单的队列中弹出时，会在结果中获得数据的先进先出顺序。
下面是优先级队列的简单实现。
# a simple implementation of priority queue
# using queue.
class priorityqueue(object):
def __init__(self):
self.queue = []
def __str__(self):
return ' '.join([str(i) for i in self.queue])
# for checking if the queue is empty
def isempty(self):
return len(self.queue) == 0
# for inserting an element in the queue
def insert(self, data):
self.queue.append(data)
# for popping an element based on priority
def delete(self):
try:
max = 0
for i in range(len(self.queue)):
if self.queue[i] > self.queue[max]:
max = i
item = self.queue[max]
del self.queue[max]
return item
except indexerror:
print()
exit()
if __name__ == '__main__':
myqueue = priorityqueue()
myqueue.insert(12)
myqueue.insert(1)
myqueue.insert(14)
myqueue.insert(7)
print(myqueue)
while not myqueue.isempty():
print(myqueue.delete())
output:
12 1 14 7
14
12
7
1
注意，在上面的代码中，delete 的时间复杂度是 o(n)。
一个更好的实现是使用，它通常用于实现优先级队列。注意 python 在库也提供 。
by using heap datastructure to implement priority queues, time complexity:
insert operation: o(log(n))
delete operation: o(log(n))
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
