priority queue底层实现

优先级队列是一种特殊的队列，它根据元素的优先级来确定出队顺序。在底层实现上，有多种数据结构可以用于实现优先级队列，其中最常见的是堆（heap）。

堆是一种完全二叉树，具有以下两个性质：
1. 堆中任意节点的值都大于等于（或小于等于）其子节点的值。
2. 堆总是一棵完全二叉树，即除了最后一层外，其他层的节点数都达到最大，并且最后一层的节点都集中在左侧。

在C++中，可以使用std::priority_queue类来实现优先级队列，该类默认使用堆作为底层数据结构。在Java中，可以使用java.util.PriorityQueue类来实现优先级队列，同样也是基于堆的实现。

堆的插入和删除操作的时间复杂度均为O(log n)，其中n是堆中元素的数量。这使得堆成为实现优先级队列的理想选择。

下面是一个使用Python heapq模块实现优先级队列的例子[^1]：

import heapq

# 创建一个空的列表作为优先级队列
queue = []

# 向优先级队列中插入元素
heapq.heappush(queue, 3)
heapq.heappush(queue, 1)
heapq.heappush(queue, 4)
heapq.heappush(queue, 2)

# 从优先级队列中弹出最小的元素
print(heapq.heappop(queue))  # 输出：1
print(heapq.heappop(queue))  # 输出：2

在这个例子中，我们使用了Python的heapq模块来实现优先级队列。通过调用heappush()函数向队列中插入元素，并且保持堆的性质；通过调用heappop()函数从队列中弹出具有最高优先级的元素。