heapq模块常用方法

发布于:2024-11-29 ⋅ 阅读:(29) ⋅ 点赞:(0)

heapq.heapify(x)

import heapq

# heapq.heapify(x)将列表x转换为堆
# 在堆数据结构中,最小元素总是位于根节点(索引为 0)
# 这个操作是在原列表上进行的,会改变列表的顺序
my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(my_list)
print(my_list)
# output:[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

heapq.heappush(heap, item)

import heapq

# 将item添加到heap堆中
# 这个操作会维护堆的性质,即将新元素插入到合适的位置,以保证堆的有序性。
my_heap = []
heapq.heappush(my_heap, 3)
heapq.heappush(my_heap, 1)
heapq.heappush(my_heap, 4)
print(my_heap)  # output:[1, 3, 4]

heapq.heappop(heap)

import heapq

# 从heap堆中弹出并返回最小的元素
# 这个操作会重新调整堆,使得剩余元素仍然保持堆的性质
my_heap = [1, 3, 4]
min_item = heapq.heappop(my_heap)
print(min_item)  # output:1
print(my_heap)  # output:[3, 4]

heapq.heapreplace(heap, item)

import heapq

# 弹出并返回堆中的最小元素,然后将item插入堆中
# 这个操作比先调用heappop()然后再调用heappush()稍微高效一些
# 因为它可以在一次操作中完成这两个步骤
my_heap = [1, 3, 4]
new_item = 0
replaced_item = heapq.heapreplace(my_heap, new_item)
print(replaced_item)  # output:1
print(my_heap)  # output:[0, 3, 4]

heapq.nlargest(n, iterable, key=None)

import heapq

# 从iterable可迭代对象中返回最大的n个元素
# 如果提供了key参数,它应该是一个接受一个参数的函数,用于从每个元素中提取比较键
my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
largest_3 = heapq.nlargest(3, my_list)
print(largest_3)

students = [
    {'name': 'Alice', 'score': 85},
    {'name': 'Bob', 'score': 92},
    {'name': 'Charlie', 'score': 78},
    {'name': 'David', 'score': 90}
]
top_two_students = heapq.nlargest(2, students, key=lambda s: s['score'])
print(top_two_students)  # output:[9, 6, 5]

heapq.nsmallest(n, iterable, key=None)

import heapq

# 从iterable可迭代对象中返回最小的n个元素
# 和nlargest类似,如果有key参数,则用于提取比较键
my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
smallest_3 = heapq.nsmallest(3, my_list)
print(smallest_3)
# output:[{'name': 'Bob', 'score': 92}, {'name': 'David', 'score': 90}]

nums = [4, 2, 7, 1]
result = heapq.nsmallest(2, nums)
print(result)  # output:[1, 1, 2]