heappop()用法 🔗

import heapq
heap = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(heapq.heappop(heap))
结果:
0
此时heap变成了 [1, 2, 3, 4, 5, 6, 7, 8, 9]

heappop(heap)的参数要求 🔗

heap只能是一个列表 🔗

heapq.heappop(heap)函数只有一个位置参数heap, 位置参数heap的数据类型只能是一个列表. 比如 heap = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

heap的元素之间必须可以进行比较运算 🔗

每次调用heappop(heap), heappop都会通过小于号<比较heap中的元素, 重新调整元素顺序, 所以heap中的各个元素之间必须是可以进行比较运算的数据类型

• 字典类型无法通过小于号<进行比较运算, 所以heap中的元素不能是字典类型
• 两个不同的数据类型是无法通过小于号<进行比较运算的, 如 5 < ‘7’ 会报错, 整型对象5无法和字符串型对象’7’进行比较运算, 所以heap中的各个元素的数据类型应当一致, 要么全是整型, 要么全是字符串型等 如 [1, 2, 3] 或 [‘1’, ‘2’, ‘3’]

堆的特性 🔗

当一个列表heap它里面的每一个元素都符合heap[0] <= heap[2*k+1]和heap[0] <= heap[2*k+2] 那么这个heap就具有堆特性(python中的堆是最小堆, 也就是说堆的索引位置0的值是堆中的最小值.)

heappop()的弹出过程 🔗

• 调用heappop(heap)会将heap[0]的值作为heappop()函数的返回值返回
• 然后heappop()会把heap[0]的值从heap中删除,并重新调整heap中元素的顺序

每次调用heappop()总是会弹出heap[0]的值 🔗

• 当heap符合堆的特性时, heapq.heappop(heap)每次弹出的都是heap中的最小值. 因为python中的堆是最小堆, 意味着heap[0]的值永远是heap中的最小值.
• 当heap不符合堆的特性时, 如果heap[0]不是heap中的最小值, 第一次调用heappop(heap)不论heap[0]是否是heap中的最小值, heappop都会弹出它, 然后heappop()会使用小于号比较heap中剩余元素的大小重新排列元素顺序, 并将剩余的元素中值最小的元素放置到heap[0]的位置, 此时heap就变成了一个heap[0]是最小值但并不符合堆特性的列表

heappop()返回值 🔗

如果heap中的元素个数大于0, 那么heappop(heap)的返回值永远是heap[0], 即heap中索引位置为0的元素的值