Python 内置模块 数据类型 heapq,bisect,reprlib

一.heapq模块
1.简介
(1)功能:

Python没有独立的堆类型,只有1个包含用于操作"堆"(heap)的函数(称为"堆队列算法"或"优先队列算法")的模块——heapq模块.该模块包含6个函数,
其中前4个与堆操作直接相关.这些API和通常的堆算法实现有所不同:①索引是从0开始的,因为Python使用从0开始的索引 ②这里实现的是"最小堆"(即
根节点为最小项的堆)而非更常见的"最大堆"(即根节点为最大项的堆)

(2)堆对象:

堆是1个二叉树,其每个父节点的值都不大于(不小于)其所有后代节点的值,故最小(最大)的元素总是在根结点(即heap[0]).为了便于比较,不存在的元
素被认为是无限大的.另外,要注意的是,堆不能保证排列的有序性(即不能保证heap[i]≤heap[i+j]),而只能保证a[i]≤a[2*i+1]且a[i]≤a[2*i+2].
Python没有独立的堆类型,故使用列表来表示堆对象

######################################################################################################################

创建堆:None=heapq.heapify(<x>)
  #注意:heapq.heapify()会直接修改传入的list并返回None
  #参数说明:
	x:指定用于创建heap的list;为list
	  #也是得到的heap

#实例:
>>> lh=[1,2,3,2,1,0,-1,0,1,2,9]
>>> heapq.heapify(lh)
>>> lh
[-1, 0, 0, 1, 1, 1, 3, 2, 2, 2, 9]

2.用于堆的方法
(1)增:

增加指定元素:heapq.heappush(<heap>,<item>)
  #参数说明:
    heap:指定堆
    item:指定要增加的元素

#实例:接上
>>> heapq.heappush(lh,3)
>>> lh
[-1, 0, 0, 1, 1, 1, 3, 2, 2, 2, 9, 3]
>>> heapq.heappush(lh,7)
>>> lh
[-1, 0, 0, 1, 1, 1, 3, 2, 2, 2, 9, 3, 7]
>>> heapq.heappush(lh,1)
>>> lh
[-1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 9, 3, 7, 3]

(2)删:

删除并返回最小的元素:[<min>=]heapq.heappop(<peap>)
  #如果希望只获得而不删除heap中最小的元素,应使用<heap>[0]
  #参数说明:
	min:返回<heap>中最小的元素

#实例:接上
>>> lh[0]
-1
>>> heapq.heappop(lh)
-1
>>> lh
[0, 0, 1, 1, 1, 1, 3, 2, 2, 2, 9, 3, 7]

(3)改:

增加指定元素再删除并返回最小的元素:[<min>=]heapq.heappushpop(<heap>,<item>)
  #相当于先调用heappush()再调用heappop(),但该方法的效率更高
删除并返回最小的元素再增加指定元素:[<min>=]heapq.heapreplace(<heap>,<item>)
  #相当于先调用heappop()再调用heappush(),但该方法的效率更高

#实例:接上
>>> heapq.heappushpop(lh,-999)
-999
>>> lh
[0, 0, 1, 1, 1, 1, 3, 2, 2, 2, 9, 3, 7]
>>> heapq.heappushpop(lh,1)
0
>>> lh
[0, 1, 1, 1, 1, 1, 3, 2, 2, 2, 9, 3, 7]
>>> heapq.heapreplace(lh,-999)
0
>>> lh
[-999, 1, 1, 1, 1, 1, 3, 2, 2, 2, 9, 3, 7]

3.基于堆的通用方法:

合并已排序的序列:[<gnrtr>=]heapq.merge([*<iterables>,key=None,reverse=False])
  #参数说明:
  	iterables:指定要合并的序列;为iterable object,并且应当已排序
  	key:指定如何从输入的元素中提取用于比较的部分;为function,默认直接比较元素
  	gnrtr:返回合并后的结果;为generator,也是已排序的

#实例:
>>> i=heapq.merge([1,2,3,4,5],[6,7,9,14])
>>> for j in i:
...     print(j)
...
1
2
3
4
5
6
7
9
14
>>> type(i)
<class 'generator'>
>>> i=heapq.merge([1,2,3,11,4,5],[6,7,9,14])#如果某些<iterables>未排序,则结果也是未排序的
>>> for j in i:
...     print(j)
...
1
2
3
6
7
9
11
4
5
14

######################################################################################################################

提取最大的n个元素:heapq.nlargest(<n>,<iterable>[,key=None])
  #参数说明:key同上
	n:指定要提取几个元素;为int
	iterable:指定数据集;为iterable object

#实例:
>>> heapq.nlargest(5,[3,1,8,-3,0,8,-2,34,9,1,-5])
[34, 9, 8, 8, 3]

######################################################################################################################

提取最小的n个元素:heapq.nsmallest(<n>,<iterable>[,key=None])
  #参数说明:同上

#实例:
>>> heapq.nsmallest(5,[3,1,8,-3,0,8,-2,34,9,1,-5])
[-5, -3, -2, 0, 1]

二.bisect模块

官方文档:https://docs.python.org/zh-cn/3.9/library/bisect.html

1.简介:

这个模块使用"二分算法"(Bisection Algorithm)来对有序列表提供支持,使其在插入新数据后仍保持有序.对于长列表,如果其插入操作十分昂贵,该
模块也可作为对常见方法的改进

2.方法:

查找指定元素的能维持列表有序的插入点:[<i>=]bisect.bisect_left(<a>,<x>[,lo=0,hi=len(a))
  #如果<x>已经存在于<a>中,插入点会在原<x>左侧
  #<i>可以将<a>分成2部分,左侧是all(val<xfor val in a[lo:i]),右侧是all(val>=x for val in a[i:lo+hi])
查找指定元素的能维持列表有序的插入点:[<i>=]bisect.bisect_right(<a>,<x>[,lo=0,hi=len(a)])
								 [<i>=]bisect.bisect(<a>,<x>[,lo=0,hi=len(a)])
  #如果<x>已经存在于<a>中,插入点会在原<x>右侧
  #参数说明:
	a:指定有序列表;为有序list
	x:指定要插入的元素
	lo,hi:分别指定使用的子序列的[起始位置的索引]和长度;均为int
	i:返回查找到的插入点的索引;为int

#实例:
>>> bisect.bisect_left([1,2,3,4,5,6,7,8],4)
3
>>> bisect.bisect([1,2,3,4,5,6,7,8],4)
4
>>> bisect.bisect_right([1,2,3,4,5,6,7,8],4)
4
>>> bisect.bisect_right([1,2,3,4,5,6,7,8],4,0,3)
3

######################################################################################################################

向有序列表中插入指定元素并维持列表有序:bisect.insort_left(<a>,<x>[,lo=0,hi=len(a)])
  #如果<x>已经存在于<a>中,新<x>会被插入到原<x>的左侧
向有序列表中插入指定元素并维持列表有序:bisect.insort_right(<a>,<x>[,lo=0,hi=len(a)])
					  			   bisect.insort(<a>,<x>[,lo=0,hi=len(a)])
  #如果<x>已经存在于<a>中,新<x>会被插入到原<x>的右侧
  #参数说明:同上

#实例:
>>> li=[1,3,6,7,8,11,12,19,22]
>>> bisect.insort_left(li,4)
>>> li
[1, 3, 4, 6, 7, 8, 11, 12, 19, 22]
>>> bisect.insort_left(li,4)
>>> li
[1, 3, 4, 4, 6, 7, 8, 11, 12, 19, 22]
>>> bisect.insort(li,4)
>>> li
[1, 3, 4, 4, 4, 6, 7, 8, 11, 12, 19, 22]
>>> bisect.insort_left(li,4,6)
>>> li
[1, 3, 4, 4, 4, 6, 4, 7, 8, 11, 12, 19, 22]

三.reprlib模块

官方文档:https://docs.python.org/zh-cn/3.9/library/reprlib.html

该模块提供了repr()的另1种实现,详情参见官方文档