在计算机领域的算法与数据结构中，堆是一种非常重要的数据结构，它在解决很多实际问题时都能发挥巨大的作用。今天咱们就来聊聊堆在一些进阶面试题中的应用，像中位数维护、滑动窗口最大值以及多路归并排序。
一、堆的基础回顾
堆其实就是一种特殊的完全二叉树，它分为大顶堆和小顶堆。大顶堆的特点是每个节点的值都大于或等于其子节点的值，而小顶堆则是每个节点的值都小于或等于其子节点的值。
在很多编程语言里，都有现成的堆结构实现。比如说 Python 里的 heapq 模块，用它就能很方便地操作堆。下面咱们来看个简单的 Python 示例：
import heapq
# 创建一个列表
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
# 将列表转换为小顶堆
heapq.heapify(nums)
# 弹出堆顶元素
smallest = heapq.heappop(nums)
print("弹出的最小元素:", smallest) # 这里会输出 1
# 插入一个新元素
heapq.heappush(nums, 0)
print("插入新元素后堆顶元素:", nums[0]) # 这里会输出 0
这个示例展示了如何使用 Python 的 heapq 模块来创建堆、弹出堆顶元素以及插入新元素。堆在很多场景下都很有用，比如优先队列，它可以根据元素的优先级来决定处理顺序。
二、中位数维护
2.1 问题描述
中位数就是一组数据按从小到大排序后，位于中间位置的数。如果数据个数是奇数，那中位数就是中间那个数；如果是偶数，中位数就是中间两个数的平均值。现在的问题是，有一组数据流，不断有新的数据加入，我们要实时维护这组数据的中位数。
2.2 解决方案
我们可以使用两个堆，一个大顶堆和一个小顶堆。大顶堆用来存储较小的一半数据，小顶堆用来存储较大的一半数据。
下面是 Python 实现的代码：
import heapq
class MedianFinder:
def __init__(self):
# 大顶堆，存储较小的一半数据
self.small = []
# 小顶堆，存储较大的一半数据
self.large = []
def addNum(self, num: int) -> None:
if len(self.small) == len(self.large):
# 先将元素加入大顶堆
heapq.heappush(self.small, -num)
# 再将大顶堆的最大值移到小顶堆
heapq.heappush(self.large, -heapq.heappop(self.small))
else:
# 先将元素加入小顶堆
heapq.heappush(self.large, num)
# 再将小顶堆的最小值移到大顶堆
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self) -> float:
if len(self.small) == len(self.large):
return (-self.small[0] + self.large[0]) / 2
else:
return self.large[0]
# 使用示例
finder = MedianFinder()
finder.addNum(1)
finder.addNum(2)
print("中位数:", finder.findMedian()) # 输出 1.5
finder.addNum(3)
print("中位数:", finder.findMedian()) # 输出 2
2.3 应用场景
中位数维护在很多领域都有应用，比如实时数据分析。在金融领域，我们可能需要实时分析股票价格的中位数，以便及时了解市场的中间价位情况。
2.4 技术优缺点
优点：使用两个堆的方法可以在 $O(log n)$ 的时间复杂度内完成插入和查找中位数的操作，效率比较高。 缺点：需要额外的空间来存储两个堆，空间复杂度为 $O(n)$。
2.5 注意事项
在实现过程中，要注意堆的插入和弹出操作的细节，特别是大顶堆在 Python 里需要用负数来模拟。
三、滑动窗口最大值
3.1 问题描述
给定一个数组和一个滑动窗口的大小，我们需要找出每个滑动窗口内的最大值。
3.2 解决方案
我们可以使用一个大顶堆来解决这个问题。每次滑动窗口移动时，将新元素加入堆中，同时将滑出窗口的元素从堆中移除，然后堆顶元素就是当前窗口的最大值。
下面是 Python 代码实现：
import heapq
from collections import deque
def maxSlidingWindow(nums, k):
n = len(nums)
# 存储元素的负值和索引
heap = [(-nums[i], i) for i in range(k)]
heapq.heapify(heap)
result = [-heap[0][0]]
for i in range(k, n):
# 加入新元素
heapq.heappush(heap, (-nums[i], i))
# 移除滑出窗口的元素
while heap[0][1] <= i - k:
heapq.heappop(heap)
result.append(-heap[0][0])
return result
# 使用示例
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print("滑动窗口最大值:", maxSlidingWindow(nums, k)) # 输出 [3, 3, 5, 5, 6, 7]
3.3 应用场景
滑动窗口最大值在很多领域都有实际应用，比如在信号处理中，我们可能需要找出一段时间内信号的最大幅值。
3.4 技术优缺点
优点：使用堆可以在 $O(log k)$ 的时间复杂度内完成插入和删除操作，整体的时间复杂度为 $O(n log k)$。 缺点：堆的维护需要一定的时间和空间开销。
3.5 注意事项
在移除滑出窗口的元素时，需要使用循环来确保堆顶元素是当前窗口内的元素。
四、多路归并排序
4.1 问题描述
假设有多个已经排好序的数组，我们要将它们合并成一个有序的数组。
4.2 解决方案
我们可以使用一个小顶堆来实现多路归并排序。首先将每个数组的第一个元素加入堆中，然后每次从堆中取出最小的元素，将其加入结果数组，同时将该元素所在数组的下一个元素加入堆中。
下面是 Python 代码实现：
import heapq
def mergeKSortedArrays(arrays):
heap = []
result = []
# 初始化堆
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
# 取出堆顶元素
val, arr_index, index = heapq.heappop(heap)
result.append(val)
# 如果该数组还有元素，将下一个元素加入堆中
if index + 1 < len(arrays[arr_index]):
heapq.heappush(heap, (arrays[arr_index][index + 1], arr_index, index + 1))
return result
# 使用示例
arrays = [[1, 4, 5], [1, 3, 4], [2, 6]]
print("多路归并排序结果:", mergeKSortedArrays(arrays)) # 输出 [1, 1, 2, 3, 4, 4, 5, 6]
3.3 应用场景
多路归并排序在数据库查询、文件合并等场景中都有广泛应用。比如在数据库中，当我们需要合并多个索引的有序结果时，就可以使用多路归并排序。
3.4 技术优缺点
优点：使用堆可以在 $O(n log k)$ 的时间复杂度内完成合并操作，其中 $n$ 是所有数组元素的总数，$k$ 是数组的个数。 缺点：需要额外的空间来存储堆，空间复杂度为 $O(k)$。
3.5 注意事项
在初始化堆时，要确保每个数组都有元素，否则会出现错误。
五、文章总结
通过上面的介绍，我们可以看到堆在中位数维护、滑动窗口最大值以及多路归并排序等问题中都有很好的应用。堆这种数据结构可以帮助我们高效地解决很多实际问题，特别是那些需要动态维护数据顺序的问题。
在使用堆时，我们要根据具体的问题选择合适的堆类型（大顶堆或小顶堆），同时要注意堆的插入、删除和查找操作的时间复杂度。另外，堆的维护需要一定的空间开销，在实际应用中要考虑空间的使用情况。
评论