likes
comments
collection
share

Python的bisect模块和堆操作

作者站长头像
站长
· 阅读数 16

在Python中,bisectheapq都是处理有序序列的常见模块,本文将分别介绍这两个模块的用法和实现方式。

bisect模块

bisect模块提供了一些函数,实现了对一个序列进行排序及维护已排序序列的一个二分查找。具体来说,bisect模块主要提供了两个函数:bisectinsort

bisect函数

bisect函数是一个通用的二分查找工具,它可以用来查找一个元素在已排序的序列中应该插入的位置,以维持序列的排序。具体用法如下:

import bisect

# 初始化一个已排序的列表
lst = [1, 3, 4, 5, 7, 9]

# 使用bisect函数查找元素插入位置
pos = bisect.bisect(lst, 6)
print(pos)

运行这段代码可以发现,变量pos输出的是4,即元素6应该插入到列表中索引为4的位置,这个列表就能保持升序排列。

insort函数

insort函数是bisect函数的变种,它可以在查找到插入位置的同时插入元素。具体用法和bisect类似,只是调用的函数不同,如下:

import bisect

# 初始化一个已排序的列表

lst = \[1, 3, 4, 5, 7, 9]

# 使用insort函数插入元素

bisect.insort(lst, 6)
print(lst)

运行这段代码可以得到输出:

\[1, 3, 4, 5, 6, 7, 9]

这个函数接受两个参数,第一个参数是已排序的序列,第二个参数是要插入的元素。该函数会将元素插入到序列的正确位置。

heapq模块

heapq模块是一个堆队列算法模块,提供了在列表上进行堆操作的函数。下面我们来看一下heapq模块如何实现堆。

初始化堆

首先,初始化一个空堆和向堆中插入元素的方法如下:

import heapq

# 初始化一个空堆

heap = \[]

# 往堆中插入元素

heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 6)

以上代码先用heap的索引为0的位置存储根节点的值,以此类推往下存储每个节点的值,然后在heap中插入元素使用的是heapq.heappush函数。插入后的堆如下图所示:

  1
   \
   3
    \
    7
   /
  6

弹出元素

从堆中弹出元素使用的是heapq.heappop函数,由于我们使用的是最小堆,根节点的值是最小的。弹出元素的代码如下:

# 从堆中弹出元素

print(heapq.heappop(heap))
print(heapq.heappop(heap))
print(heapq.heappop(heap))
print(heapq.heappop(heap))

运行以上代码可以看到输出:

1
3
6
7

这里的堆是使用数组实现的最小堆(根节点的值是最小的),如果要实现最大堆,可以在插入元素时取反,在弹出元素时再取反。

总结

Python的bisect模块和heapq模块分别用来操作有序序列和堆。bisect模块提供了二分查找和插入元素的函数,heapq模块则提供了堆操作的函数。熟练使用这些模块能够提高编码效率,并加深对数据结构和算法的理解。

转载自:https://juejin.cn/post/7241562753164656701
评论
请登录