前言
大家好！今天我想和大家分享如何使用TypeScript实现一个优先队列（Priority Queue），并利用它来解决LeetCode第215题——数组中的第K个最大元素。在算法面试中，优先队列是一个非常常用的数据结构，理解并能熟练实现它对我们解决一系列问题都有帮助。
问题描述
LeetCode第215题：数组中的第K个最大元素
给定一个未排序的整数数组 nums，找到其中第 k 个最大的元素。
示例：
输入: nums = [3,2,1,5,6,4], k = 2
输出: 5
输入: nums = [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
- 1 ≤ k ≤ nums.length ≤ 10^4
- -10^4 ≤ nums[i] ≤ 10^4
解题思路
要找到第 k 个最大的元素，我们可以采用多种方法：
- 排序法：将数组排序，然后取第
k个最大的元素。时间复杂度为 O(n log n)。 - 基于堆的优先队列：使用一个大小为
k的最小堆来维护当前最大的k个元素。时间复杂度为 O(n log k)。 - 快速选择算法：类似快速排序的分区思想，平均时间复杂度为 O(n)。
在这篇文章中，我们重点介绍使用最小堆实现的优先队列，因为它在实际应用中非常高效，且实现相对简单。
什么是优先队列？
优先队列是一种特殊的队列，元素按照优先级进行出入队操作。常用的实现方式是堆，根据堆的性质，可以快速地获取当前的最值（最大值或最小值）。
在我们的问题中，我们需要维护一个大小为 k 的最小堆，堆顶元素就是当前第 k 个最大的元素。
TypeScript中实现最小堆
堆的基本操作
- 插入元素（insert）：将新元素添加到堆的末尾，然后向上调整位置（上浮）。
- 删除堆顶元素（extractMin）：移除堆顶元素，将末尾元素放到堆顶，然后向下调整位置（下沉）。
- 查看堆顶元素（getMin）：获取堆顶元素的值。
- 获取堆的大小（size）：返回堆中元素的数量。
实现代码
class MinHeap {
private heap: number[] = [];
insert(val: number): void {
this.heap.push(val);
this.bubbleUp();
}
private bubbleUp(): void {
let index = this.heap.length - 1;
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index] >= this.heap[parentIndex]) break;
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
extractMin(): number | undefined {
if (this.heap.length === 0) return undefined;
const min = this.heap[0];
const end = this.heap.pop()!;
if (this.heap.length > 0) {
this.heap[0] = end;
this.sinkDown();
}
return min;
}
private sinkDown(): void {
let index = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIdx = 2 * index + 1;
let rightChildIdx = 2 * index + 2;
let swapIdx: number | null = null;
if (leftChildIdx < length) {
if (this.heap[leftChildIdx] < element) {
swapIdx = leftChildIdx;
}
}
if (rightChildIdx < length) {
if (
(swapIdx === null && this.heap[rightChildIdx] < element) ||
(swapIdx !== null && this.heap[rightChildIdx] < this.heap[leftChildIdx])
) {
swapIdx = rightChildIdx;
}
}
if (swapIdx === null) break;
[this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
index = swapIdx;
}
}
getMin(): number | undefined {
return this.heap[0];
}
size(): number {
return this.heap.length;
}
}
代码解释
- insert(val: number)：将元素添加到堆末尾，然后调用
bubbleUp进行上浮操作，保持最小堆性质。 - bubbleUp()：从新添加的元素开始，与父节点比较，如果小于父节点则交换位置，直到满足最小堆性质。
- extractMin()：移除并返回堆顶元素，将堆末尾元素放到堆顶，然后调用
sinkDown进行下沉操作。 - sinkDown()：从堆顶开始，与子节点比较，如果大于子节点则交换位置，直到满足最小堆性质。
- getMin()：返回堆顶元素，不修改堆。
- size()：返回堆中元素的数量。
利用最小堆解决第K个最大元素问题
实现思路
- 创建一个大小为
k的最小堆。 - 遍历数组，将元素逐一插入堆中。
- 当堆的大小超过
k时，移除堆顶元素（最小值）。 - 遍历完成后，堆顶元素就是第
k个最大元素。
实现代码
function findKthLargest(nums: number[], k: number): number {
const minHeap = new MinHeap();
for (const num of nums) {
minHeap.insert(num);
if (minHeap.size() > k) {
minHeap.extractMin();
}
}
return minHeap.getMin()!;
}
代码解释
- 遍历数组：将每个元素插入到最小堆中。
- 维护堆的大小：如果堆的大小超过
k，则移除堆顶元素，确保堆中始终只包含当前最大的k个元素。 - 返回结果：遍历结束后，堆顶元素即为第
k个最大元素。
测试代码
const nums1 = [3, 2, 1, 5, 6, 4];
const k1 = 2;
console.log(findKthLargest(nums1, k1)); // 输出: 5
const nums2 = [3, 2, 3, 1, 2, 4, 5, 5, 6];
const k2 = 4;
console.log(findKthLargest(nums2, k2)); // 输出: 4
时间复杂度分析
- 插入和移除操作：每次操作的时间复杂度为 O(log k)。
- 总时间复杂度：对于长度为
n的数组，总的时间复杂度为 O(n log k)，当k远小于n时，效率较高。
空间复杂度分析
- 空间复杂度：使用了额外的堆空间，最大为 O(k)。
总结
通过使用最小堆实现的优先队列，我们可以高效地找到数组中的第 k 个最大元素。这种方法在处理大规模数据时非常实用，因为我们不需要对整个数组进行排序，只需维护一个大小为 k 的堆即可。
优点
- 高效性：时间复杂度为 O(n log k)，比直接排序的 O(n log n) 更优。
- 适用性强：当需要实时处理数据流并获取第
k个最大元素时，此方法非常适用。
缺点
- 实现复杂度：相比内置排序函数，手动实现堆需要更多的代码和调试。
后记
希望这篇文章能帮助大家理解如何在TypeScript中实现优先队列，并应用于实际问题。如果有任何疑问或改进建议，欢迎在评论区与我交流！
参考资料
感谢阅读！如果觉得有帮助，请点赞支持。