小顶堆、大顶堆和Top-k问题

小顶堆初始化

import heapq# 无序的列表
nums = [3, 2, 5, 1, 4]# 将列表转换为堆
heapq.heapify(nums)# 输出结果
print(nums)  # 输出: [1, 2, 5, 3, 4]，最小值 1 在堆顶

大顶堆初始化

import heapq# 实现最大堆的方法：将元素取负
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5]# 构建最大堆
max_heap = [-num for num in nums]
heapq.heapify(max_heap)# 弹出最大值（负数的最小值就是最大值）
max_value = -heapq.heappop(max_heap)print(max_value)  # 输出: 9

Top-k问题

https://www.hello-algo.com/chapter_heap/top_k/#832

def top_k_heap(nums: list[int], k: int) -> list[int]:"""基于堆查找数组中最大的 k 个元素"""# 初始化小顶堆heap = []# 将数组的前 k 个元素入堆for i in range(k):heapq.heappush(heap, nums[i])# 从第 k+1 个元素开始，保持堆的长度为 kfor i in range(k, len(nums)):# 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆if nums[i] > heap[0]:heapq.heappop(heap)heapq.heappush(heap, nums[i])return heap

力扣215. 数组中的第K个最大元素

import heapq
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:heap = []for i in range(k):heapq.heappush(heap, nums[i])for i in range(k, len(nums)):if nums[i] > heap[0]:heapq.heappop(heap)heapq.heappush(heap, nums[i])return heap[0]