第五章：二叉堆 (Binary Heaps)

学习内容

二叉堆是一种特殊的完全二叉树，具有堆性质，是实现优先级队列的重要数据结构。

二叉堆基础

#### 定义

• 最大堆：父节点的值总是大于或等于任何一个子节点的值

• 最小堆：父节点的值总是小于或等于任何一个子节点的值

#### 特性

• 完全二叉树：除了最后一层，其他层都被完全填满，最后一层的节点都靠左排列

• 堆性质：父节点与子节点之间满足特定的大小关系

存储方式

二叉堆通常使用数组存储，对于索引为 i 的节点：

• 父节点索引：(i-1)/2

• 左子节点索引：2*i+1

• 右子节点索引：2*i+2

核心操作

#### 上浮（Swim）

当节点的值违反了堆性质时，需要将其向上移动以恢复堆性质。

#### 下沉（Sink）

当节点的值违反了堆性质时，需要将其向下移动以恢复堆性质。

#### 插入元素

1. 将新元素添加到堆的末尾
2. 执行上浮操作恢复堆性质

#### 删除堆顶

1. 将堆顶元素与末尾元素交换
2. 删除末尾元素
3. 执行下沉操作恢复堆性质

重点和难点

重点

1. 理解二叉堆的性质和特点
2. 掌握堆的核心操作：上浮和下沉
3. 理解优先级队列的概念和应用

难点

1. 上浮和下沉操作的实现细节
2. 堆的数组表示和索引计算
3. 堆操作的时间复杂度分析

练习题

堆的基本操作

1. 数组中的第K个最大元素 (Kth Largest Element in an Array)
- 题目：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
- 解题思路：使用最小堆维护前k个最大元素，堆顶即为第k大元素。
- 注意点：注意堆的大小控制，避免不必要的元素存储。

2. 前K个高频元素 (Top K Frequent Elements)
- 题目：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
- 解题思路：先统计频率，然后使用最小堆维护前k个高频元素。
- 注意点：需要先进行频率统计，再进行堆操作。

堆的应用

1. 合并K个升序链表 (Merge k Sorted Lists)
- 题目：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中。
- 解题思路：使用最小堆维护所有链表的头节点，每次取出最小节点并添加其下一个节点到堆中。
- 注意点：需要处理链表遍历完的情况。

2. 滑动窗口最大值 (Sliding Window Maximum)
- 题目：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
- 解题思路：使用双端队列维护可能成为最大值的元素索引，保持队列单调递减。
- 注意点：需要处理窗口滑动时元素的进出，维护队列的有效性。

解题思路总结

优先级队列的应用场景

1. Top K 问题：找最大/最小的K个元素
2. 调度问题：按优先级处理任务
3. 图算法：Dijkstra算法、最小生成树等

堆操作的时间复杂度

• 插入元素：O(log n)

• 删除堆顶：O(log n)

• 查找最值：O(1)

堆与其他数据结构的比较

• 与排序数组比较：插入O(n) vs O(log n)，查找O(1) vs O(1)

• 与平衡BST比较：插入O(log n) vs O(log n)，但堆常数更小，实现更简单

学习时间

建议学习时间：0.5-1天

• 二叉堆基础和核心操作：45分钟

• 优先级队列应用：30分钟

• 练习题：1小时