博客

详解Python 优先队列

  • Post category:Python

下面是Python优先队列使用方法的完整攻略。

Python优先队列使用方法

1. 前言

Python中的优先队列是通过heapq模块实现的，使用起来非常简单。优先队列是一种数据结构，具有队列的特点，但是每次出队的元素是优先级最高的元素，而不是在队列中存放时间最久的元素。

2. 使用方法

2.1 创建优先队列

使用Python中的列表来创建优先队列，列表内元素的顺序即为元素的优先级。

import heapq

pq = [2, 4, 1, 6, 5, 3]
heapq.heapify(pq)
print(pq)   # 输出：[1, 4, 2, 6, 5, 3]

2.2 插入元素

使用heapq.heappush()方法可以向优先队列中插入元素。

import heapq

pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 3)
heapq.heappush(pq, 7)
print(pq)   # 输出：[3, 5, 7]

2.3 弹出元素

使用heapq.heappop()方法可以弹出优先级最高的元素。

import heapq

pq = [2, 4, 1, 6, 5, 3]
heapq.heapify(pq)
print(heapq.heappop(pq))    # 输出：1
print(pq)   # 输出：[2, 4, 3, 6, 5]

3. 示例说明

下面通过两个示例说明优先队列的使用方法。

3.1 找出无序列表中第K大的元素

import heapq

def find_kth_largest(nums, k):
    pq = nums[:k]
    heapq.heapify(pq)
    for i in range(k, len(nums)):
        if nums[i] > pq[0]:
            heapq.heappop(pq)
            heapq.heappush(pq, nums[i])
    return pq[0]

nums = [3, 6, 1, 8, 2, 5]
k = 2
print(find_kth_largest(nums, k))    # 输出：6

3.2 合并K个有序列表

import heapq

def merge_k_lists(lists):
    pq = [(lists[i][0], i, 0) for i in range(len(lists)) if len(lists[i]) > 0]
    heapq.heapify(pq)
    res = []
    while pq:
        cur_val, cur_i, cur_j = heapq.heappop(pq)
        res.append(cur_val)
        if cur_j + 1 < len(lists[cur_i]):
            next_val = lists[cur_i][cur_j + 1]
            heapq.heappush(pq, (next_val, cur_i, cur_j + 1))
    return res

lists = [[1, 3, 5], [2, 4, 6], [3, 6, 9]]
print(merge_k_lists(lists))    # 输出：[1, 2, 3, 3, 4, 5, 6, 6, 9]

以上便是Python优先队列使用方法的详细攻略。

Tags: