python计算最大优先级队列实例

Python实现最大优先级队列的方式

1. 定义优先级队列

我们可以通过以下方式定义一个优先级队列：

class PriorityQueue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

    def enqueue(self, item, priority):
        # 优先级高的在队首，优先级相同时，先插入的在前面
        index = 0
        for i, (p, _) in enumerate(self.items):
            if priority >= p:
                index = i+1
            else:
                break
        self.items.insert(index, (priority, item))

    def dequeue(self):
        return self.items.pop()[1]

    def peek(self):
        return self.items[-1][1]

    def __str__(self):
        return str(self.items)

在以上代码中，

• __init__ 方法初始化了一个空列表用于存储队列元素；
• is_empty 方法检查队列是否为空；
• size 方法返回队列长度；
• enqueue 方法接收两个参数，一个是元素，一个是优先级，按照优先级高低插入队列；
• dequeue 方法弹出队列中优先级最高的元素；
• peek 方法返回队列中优先级最高的元素，但是不弹出；
• __str__ 方法将队列转成字符串输出。

2. 示例说明

2.1 一般情况

q = PriorityQueue()
q.enqueue('C', 5)
q.enqueue('A', 10)
q.enqueue('B', 7)
print(q) # 输出 [(10, 'A'), (7, 'B'), (5, 'C')]
print(q.dequeue()) # 输出 A
print(q.peek()) # 输出 B
print(q) # 输出 [(7, 'B'), (5, 'C')]

以上代码首先初始化一个新的优先级队列 q，然后按照优先级高低依次插入三个元素。调用 enqueue 方法之后，队列中的元素顺序是：A、B、C。然后依次调用 dequeue 和 peek 方法获取队列中优先级最高的元素，得到 A 和 B。最后打印队列时，元素顺序变成了 B、C。

2.2 优先级相同时

q = PriorityQueue()
q.enqueue('C', 5)
q.enqueue('A', 5)
q.enqueue('B', 5)
print(q) # 输出 [(5, 'C'), (5, 'A'), (5, 'B')]
print(q.dequeue()) # 输出 C
print(q.peek()) # 输出 A
print(q) # 输出 [(5, 'A'), (5, 'B')]

以上代码同样初始化一个新的优先级队列 q，然后插入三个优先级相等的元素。队列中的元素顺序是：C、A、B，因为插入顺序的先后。然后依次调用 dequeue 和 peek 方法获取队列中优先级最高的元素，得到 C 和 A。最后打印队列时，元素顺序变成了 A、B。