heapq 是 Python 标准库中的一个模块，提供了堆（heap）队列算法的实现。堆是一种特殊的树形数据结构，常用于实现优先队列。

heapq.nsmallest方法

heapq 模块提供了一些函数来操作堆，其中 heapq.nsmallest 可以用来找到数组中最小的 k 个元素。 heapq.largest 可以用来找到数组中最大的 k 个元素。

语法：heapq.nsmallest(k, iterable, key=None)

• 参数：

• k：需要找到的最小元素的个数。

• iterable：要从中寻找最小元素的可迭代对象。

• key：一个函数，如果提供了这个参数，它会被用来从每个元素中提取一个用于比较的键。默认为 None，即直接比较元素。

• 返回值：返回一个包含 k 个最小元素的列表，按照它们在原可迭代对象中的顺序排列。

• 时间复杂度：heapq.nsmallest 的时间复杂度为 O(n log k)，其中 n 是可迭代对象的长度。

heapq 模块的其他常用函数

• heapq.heappush(heap, item)：将 item 添加到堆中。

• heapq.heappop(heap)：从堆中弹出并返回最小的元素。

• heapq.heapify(x)：将列表 x 转换为堆，原地，线性时间内完成。

• heapq.nlargest(n, iterable, key=None)：返回 iterable 中最大的 n 个元素。

算法题

题目 1: 找到数组中的前 K 大元素

题目描述： 给定一个整数数组 nums 和一个整数 k，返回数组中前 k 大的元素。

输入: nums = [3, 2, 1, 5, 6, 4], k = 2
输出: [5, 6]

import heapq

def find_k_largest(nums,k):
      #前k大
      return heapq.nlargest(nums,k)#前k大
      #前k小
      #return heapq.nsmallest(nums,k)
print(find_k_largest(nums,k))

题目 2: 合并 K 个排序链表

题目描述： 给定 k 个排序链表，合并它们成一个排序的链表并返回。

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __lt__(self, other):
        return self.val < other.val

def merge_k_lists(lists):
    heap = []
    for l in lists:
        if l:
            heapq.heappush(heap, l)

    dummy = ListNode(0)
    current = dummy

    while heap:
        node = heapq.heappop(heap)
        current.next = node
        current = current.next
        if node.next:
            heapq.heappush(heap, node.next)

    return dummy.next

# 示例
# 创建链表
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# 打印链表
def print_linked_list(head):
    vals = []
    while head:
        vals.append(head.val)
        head = head.next
    print("->".join(map(str, vals)))

lists = [
    create_linked_list([1, 4, 5]),
    create_linked_list([1, 3, 4]),
    create_linked_list([2, 6])
]

merged_head = merge_k_lists(lists)
print_linked_list(merged_head)  # 输出: 1->1->2->3->4->4->5->6