双端优先级队列（Double-Ended Priority Queue）是一种支持在两端进行插入和删除操作的优先级队列。它可以在 O(log n) 的时间复杂度内完成插入、删除、查询操作。双端优先级队列可以使用二叉堆或线段树等数据结构实现。
使用双端优先级队列时，首先需要创建一个双端优先级队列实例，并提供一个初始化的队列。接下来，可以进行插入、删除和查询操作。
- 插入：在双端优先级队列中插入一个元素，可以将其与当前堆顶元素进行合并，如果合并后堆的大小不变，则直接插入；否则，将堆顶元素与左右子节点合并，重新调整堆结构。
- 删除：在双端优先级队列中删除一个元素，可以将其与当前堆底元素进行合并，如果合并后堆的大小不变，则直接删除；否则，将堆底元素与左右子节点合并，重新调整堆结构。
- 查询：查询双端优先级队列中的最小元素，可以直接获取堆顶元素。
在解决一些涉及优先级队列的问题时，可以使用双端优先级队列来维护候选解，并在需要时按照一定的优先级进行选择。双端优先级队列的一个典型应用场景是求解旅行商问题（TSP, Traveling Salesman Problem），可以使用线段树实现双端优先级队列，在 O(log n) 的时间复杂度内完成 TSP 的求解。
以下是一个简单的 Python 实现示例，使用二叉堆实现双端优先级队列：
import heapq
class DoubleEndedPriorityQueue:
def init(self):
self.heap = []
def insert(self, item):
heapq.heappush(self.heap, item)
def delete(self):
if not self.heap:
return None
min_item = heapq.heappop(self.heap)
heapq.heapify(self.heap)
return min_item
def get_min(self):
if not self.heap:
return None
return self.heap[0]
示例
pq = DoubleEndedPriorityQueue()
pq.insert(5)
pq.insert(3)
pq.insert(8)
pq.insert(1)
print(pq.get_min()) # 输出 1
pq.delete()
print(pq.get_min()) # 输出 3
pq.delete()
print(pq.get_min()) # 输出 5
CopyCopy
在这个示例中，我们创建了一个双端优先级队列，并使用二叉堆实现。我们定义了插入、删除和查询操作，并在示例中展示了如何使用双端优先级队列。
