【Python标准库】heapq&bisect

2017年09月11日    Author:Guofei

文章归类: 0xb0_Python语法    文章编号: 1222


版权声明:本文作者是郭飞。转载随意,但需要标明原文链接,并通知本人
原文链接:https://www.guofei.site/2017/09/11/heapq.html

Edit

heapq 模块提供堆算法,官方文档写的很好,摘抄下来(对格式和段落进行了整理):

NAME:

This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm.

heapq 实现了 heap queue 算法(也叫做 priority queue algorithm)

DESCRIPTION

Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This implementation uses arrays for which heap[k] <= heap[2k+1] and heap[k] <= heap[2k+2] for all k, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that its smallest element is always the root, heap[0].


bisect

bisect 一个二分法的库,最大的价值是提供一个二分法算法示例

import bisect

a=[1,2,3,3,5,6,7]

# 找到可以把 x 插入 a 的 index,使得 a 仍然能保持顺序
# 其中,a 是 升序的 list,x 是 value
bisect.bisect_left(a=a,x=3,lo=0,hi=len(a)) # 遇到 x in a 的情况,输出最左边的可插入的index
bisect.bisect_right(a=a,x=3) # 遇到 x in a 的情况,输出最右边可插入的 index (注意,a中最右边的index)
bisect.bisect(a=a,x=3) # 完全等价于 bisect.bisect_right


bisect.insort_left(a=a,x=4,lo=0,hi=len(a))
# equivalent to a.insert(bisect.bisect_left(a, x, lo, hi), x)
# 记住,虽然 binary search 是 O(lg n)的,但 insert 是 O(n) 的
bisect.insort_right(a=a,x=4,lo=0,hi=len(a))
# a.insert(bisect.bisect_right(a, x, lo, hi), x)

应用举例

想把百分制的考试成绩,转化为’ABCDF’这种标志

breakpoints = [60, 70, 80, 90] # 隔断区间
grades = 'FDCBA' # 标志
scores = [33, 99, 77, 70, 89, 90, 100] # 同学们的分数
[grades[bisect.bisect_left(a=breakpoints,x=i)] for i in scores]

参考文献

https://docs.python.org/3/


您的支持将鼓励我继续创作!
WeChatQR AliPayQR qr_wechat