Python中的优先队列(priority queue)和堆(heap)

什么是优先队列(priority queue)和堆(heap)

优先队列(priority queue)是一种数据结构，它是一个元素集合，每个元素都有一个优先级。当加入新元素时，它会自动放到正确的位置，以使集合中优先级最高的元素总是最先被取出。堆(heap)是一种数据结构，它可以用来实现优先队列。堆是一棵完全二叉树，每个节点都满足堆性质，即它的值大于等于（或小于等于）它的子节点的值。在堆中，最小（或最大）元素总是在根节点，这使得在插入或删除元素时，堆保持了它的结构性。

Python中的优先队列(priority queue)

在Python中，标准库提供了一个优先队列模块，名为 queue，该模块实现了优先队列的基本操作。Python中的优先队列可以是非破坏性的，这意味着它支持查看队列中的下一个元素而不将其弹出。Python中的优先队列实现了一个基于堆的优先队列，在这个实现中，较低的数拥有更高的优先级。

优先队列(priority queue)的基本操作

创建一个空的优先队列：

import queue
q = queue.PriorityQueue()

将元素放入优先队列：

q.put((优先级, 元素))

获取并移除当前优先队列中最小的元素：

q.get()

查看但是不移除当前优先队列中最小的元素：

q.queue[0]

判断优先队列是否为空：

q.empty()

示例说明

下面的示例说明了如何使用Python中的优先队列来解决一个排序问题。

问题描述：

给定一个字符串列表，对其进行排序，要求按照字符串中包含的数字从小到大排序，数字不在字符串中的字符串排在前面。

示例输入：

lst = ['a1.txt', 'b3.txt', 'c2.txt', 'd.txt', 'e5.txt', 'f.txt']

示例输出：

['d.txt', 'f.txt', 'a1.txt', 'c2.txt', 'b3.txt', 'e5.txt']

解题步骤：

1. 创建一个空的优先队列
2. 遍历输入的字符串列表，对于每一个字符串，将其拆分成数字和非数字部分
3. 如果字符串中包含数字，将其转换为整数，否则将其设为0
4. 将转换后的字符串和原始字符串作为一个元组加入优先队列中，元组中第一个元素为字符串中包含的数字，第二个元素为原始字符串
5. 逐个从优先队列中取出元素，直到队列为空，取出的元素中第二个元素即为排序后的字符串列表

以下是完整代码实现：

def sort_str_list(lst):
    q = queue.PriorityQueue()
    for s in lst:
        m = re.search(r'\d+', s)
        if m:
            num = int(m.group(0))
        else:
            num = 0
        q.put((num, s))
    res = []
    while not q.empty():
        res.append(q.get()[1])
    return res

Python中的堆(heap)

Python中也有一个堆模块，名为 heapq，由于它实现了一些底层的堆操作，因此可以非常高效地操作大型数据集。Python中的堆模块实现了以下操作：

heapq.heappop(heap)
heapq.heappush(heap, item)
heapq.heapreplace(heap, item)
heapq.heappushpop(heap, item)
heapq.heapify(x)
heapq.nlargest(n, iterable, key=None)
heapq.nsmallest(n, iterable, key=None)

其中，最常用的是 heappush 和 heappop，它们分别用于将元素加入堆和获取并移除堆中的最小元素。

示例说明

下面的示例说明了如何使用Python中的堆来解决一个问题：找到数据集中的第k大元素。

问题描述：

给定一个整数列表，找到其中第k大的元素。

示例输入：

lst = [3, 2, 1, 5, 6, 4]
k = 2

示例输出：

5

解决步骤：

1. 创建一个大小为k的最小堆
2. 遍历输入的列表，对于每个元素，将其加入最小堆中
3. 如果最小堆大小大于k，则移除堆顶元素
4. 返回堆顶元素

以下是完整代码实现：

import heapq

def find_kth_largest(lst, k):
    heap = []
    for num in lst:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

可以看到，在这个示例中，使用Python中的堆模块来解决问题非常高效，对于大型数据集也可以很好地处理。