Python递归实现优先队列数据结构
优先队列是一种特殊的队列，根据每个元素的优先级来确定出队顺序，具有优先级高的元素先出队的特点。常用的实现方式是使用堆（最小堆或最大堆），但我们也可以使用递归实现优先队列。
具体实现思路如下：
- 定义一个类，用于存储元素和其优先级信息。
- 定义一个空列表，用于存储所有元素。
- 定义一个递归函数，用于将新元素插入到列表中，并保持列表按照优先级排序。
- 定义一个出队函数，用于弹出优先级最高的元素。
以下是实现代码：
class PriorityQueue: def __init__(self): self.elements = [] def insert(self, item, priority): self.elements.append((item, priority)) self._sort() def _sort(self): self.elements = sorted(self.elements, key=lambda x: x[1], reverse=True) def pop(self): return self.elements.pop(0)[0]
以上代码中，我们通过元素和优先级组成一个元组，将其作为一个整体存储在列表中。在插入新元素时，将其与优先级一起存储，并调用 _sort 函数，按照优先级排序所有元素。在弹出优先级最高的元素时，直接弹出第一个元素即可。
示例代码：
q = PriorityQueue() q.insert("pidancode.com", 1) q.insert("hello", 3) q.insert("world", 2) print(q.pop()) print(q.pop()) print(q.pop())
输出：
hello world pidancode.com
以上代码中，我们创建了一个优先队列 q，并分别插入三个元素。由于 hello 的优先级最高，因此第一次弹出的是它。接着，由于 world 的优先级次高，因此第二次弹出的是它。最后，由于 pidancode.com 的优先级最低，因此最后弹出的是它。
相关文章