Heap

算法思路：

最小堆可以维持堆顶元素为最小值。

应用：

1. 求数组第k个大的数

Python代码：

from heapq import heapreplace, heappush
def min_heap(self, nums: List[int], k: int) -> List[int]:
	res = []
	for i in range(len(nums)):
		if i < k:
			heappush(res, nums[i])
		elif nums[i] > res[0]:
			heapreplace(res, nums[i])

	return res

max heap的话，入堆的数转负数，跟堆顶比较的大于号不变，出堆后转为整数
注意第6行res[0]并没有负号，因为res已经是负数

def max_heap(self, nums: List[int], k: int) -> List[int]:
	res = []
	for i in range(len(nums)):
		if i < k:
			heappush(res, -nums[i])
		elif -nums[i] > res[0]:
			heapreplace(res, -nums[i])
	res = [-n for n in res]
	return res

BFS + Heap

def bfs(self, nums, start, k) -> List[int]:
	heap, res = ([start])), []
	visited.add(start)
	while heap:
		node = heapq.heappop(heap)
		res.append(node)
		if len(res) == k:
			break
		for neighbor in graph[node]:
			if neighbor in visited:
				continue
			heap.append(neighbor)
			visited.add(neighbor)
	return res

算法分析：

时间复杂度为O(nlogk)，空间复杂度O(1)。