博客

python 堆和优先队列的使用详解

  • Post category:Python

Python堆和优先队列的使用详解

什么是堆？

堆是一种特殊的数据结构，它是一棵二叉树，满足以下两个特性：

  1. 堆是一颗完全二叉树；
  2. 堆中每个结点的值都大于等于或小于等于左右孩子结点的值。

我们将值较小的称为小根堆，将值较大的称为大根堆。Python提供了heapq模块以支持堆的操作。

堆的应用场景

堆的典型应用场景是对数据进行排序（优先级队列），或找出最大或最小的元素。常见的场景如算法题中的Dijkstra算法、哈夫曼编码等。

常用堆的操作

1.堆的初始化

在Python中，可以使用heapq模块初始化堆。

import heapq

nums = [6, 2, 3, 5, 1, 8, 7]

heapq.heapify(nums)
print(nums)

输出：

[1, 2, 3, 5, 6, 8, 7]

2.堆的插入元素

在堆中插入一个元素可以使用heapq的heappush()函数实现。

import heapq

nums = [1, 2, 3, 5, 6, 8, 7]

heapq.heappush(nums, 4)
print(nums)

输出：

[1, 2, 3, 5, 4, 8, 7, 6]

3.堆中删除元素

堆中删除元素可以使用heapq的heappop()函数实现。

import heapq

nums = [1, 2, 3, 5, 4, 8, 7, 6]

heapq.heappop(nums)
print(nums)

输出：

[2, 4, 3, 5, 6, 8, 7]

4.堆中元素的查找

堆中的元素可以使用heapq的heapreplace()函数进行查找。

import heapq

nums = [1, 2, 3, 5, 4, 8, 7, 6]

heapq.heapreplace(nums, 0)
print(nums)

输出：

[0, 2, 3, 5, 4, 8, 7, 6]

5.堆的合并

堆的合并可以通过heapq模块提供的heappushpop()函数实现。

import heapq

nums1 = [1, 2, 3, 5, 4]
nums2 = [6, 8, 7, 9]

heapq.heapify(nums1)
heapq.heapify(nums2)

heapq.heappushpop(nums1, 0)
heapq.heappushpop(nums1, 10)

nums = heapq.heappushpop(nums1, heapq.heappop(nums2))
nums += heapq.heappop(nums2)

print(nums1)
print(nums2)
print(nums)

输出：

[2, 4, 3, 5, 10]
[7, 8, 9]
0

示例1：使用堆实现优先队列

优先队列是一种存储顺序和访问顺序不同的队列，元素在插入到队列中时会被赋予一个优先级，可以随时获得队列中优先级最高的元素。

在Python中，可以使用堆实现优先队列。在以下示例中，每个元素都是一个元组，第一个元素为优先级，第二个元素为任务。

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, priority, task):
        heapq.heappush(self._queue, (-priority, self._index, task))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

q = PriorityQueue()
q.push(1, 'task1')
q.push(3, 'task2')
q.push(2, 'task3')
q.push(5, 'task4')
print(q.pop())
print(q.pop())
print(q.pop())
print(q.pop())

输出：

task4
task2
task3
task1

示例2：使用堆进行排序

在Python中，可以使用heapq模块对列表进行原地排序。

import heapq

nums = [6, 2, 3, 5, 1, 8, 7]

heapq.heapify(nums)
print([heapq.heappop(nums) for _ in range(len(nums))])

输出：

[1, 2, 3, 5, 6, 7, 8]

以上就是Python堆和优先队列的使用详解，希望能对大家有所帮助。

Tags: