使用堆解决Top K 问题

# 1.1 堆的基本原理

堆是一种特殊的完全二叉树，它满足以下性质：

- **堆序性：**对于每个非叶节点，其值都大于或等于其左右子节点的值。
- **完全性：**除了最后一层外，所有层都完全填充，最后一层从左到右尽可能填充。

堆的实现通常使用数组，其中根节点存储在数组的第一个元素中，其左右子节点分别存储在数组的第 2 和第 3 个元素中，依此类推。

堆的基本操作包括：

- **插入：**将一个元素插入堆中，保持堆序性。
- **删除：**删除堆顶元素，保持堆序性。
- **调整：**调整堆中某个元素的位置，保持堆序性。

# 2. 堆的应用技巧

堆是一种高效的数据结构，除了基本的存储和检索操作外，它还具有广泛的应用场景。本章节将介绍堆在排序、选择、合并和分割等方面的应用技巧。

### 2.1 堆的排序和选择

#### 2.1.1 堆排序的算法和复杂度分析

堆排序是一种基于堆的数据排序算法。它的基本思想是将待排序的元素构建成一个最大堆，然后依次弹出堆顶元素，得到一个从小到大有序的序列。

**算法步骤：**

1. 将待排序的元素构建成一个最大堆。
2. 将堆顶元素与最后一个元素交换，弹出堆顶元素。
3. 对剩余的元素重新构建最大堆。
4. 重复步骤 2 和 3，直到堆中只剩下一个元素。

**复杂度分析：**

* 时间复杂度：O(n log n)，其中 n 为待排序元素的个数。
* 空间复杂度：O(1)，因为算法不需要额外的空间。

#### 2.1.2 Top K 问题的堆解法

Top K 问题是指在给定一个无序数组中找到最大的 K 个元素。使用堆可以高效地解决该问题。

**算法步骤：**

1. 将前 K 个元素构建成一个小根堆。
2. 遍历剩余的元素，如果当前元素大于堆顶元素，则弹出堆顶元素并插入当前元素。
3. 重复步骤 2，直到遍历完所有元素。

**复杂度分析：**

* 时间复杂度：O(n log k)，其中 n 为待排序元素的个数，k 为要查找的 Top K 个元素的个数。
* 空间复杂度：O(k)，因为算法需要维护一个大小为 k 的小根堆。

### 2.2 堆的合并和分割

#### 2.2.1 堆的合并操作

堆的合并是指将两个有序的堆合并成一个新的有序堆。该操作可以用于合并多个有序数据集合。

**算法步骤：**

1. 将两个堆的根节点进行比较，较小的节点作为新堆的根节点。
2. 将较小的节点的子树作为新堆的左子树或右子树。
3. 递归地将较大的节点的子树合并到新堆中。

**复杂度分析：**

* 时间复杂度：O(log n)，其中 n 为两个堆中元素的总数。
* 空间复杂度：O(1)，因为算法不需要额外的空间。

#### 2.2.2 堆的分割操作

堆的分割是指将一个有序的堆分割成两个有序的堆。该操作可以用于将一个有序数据集合拆分为多个有序子集。

**算法步骤：**

1. 将堆顶元素弹出并保存。
2. 将堆的剩余部分递归地分割成两个子堆。
3. 将保存的堆顶元素插入到较小的子堆中。

**复杂度分析：**

* 时间复杂度：O(log n)，其中 n 为堆中元素的个数。
* 空间复杂度：O(1)，因为算法不需要额外的空间。

# 3.1 基于堆的优先队列

#### 3.1.1 优先队列的定义和实现

优先队列是一种抽象数据结构，它支持以下操作：

- `push(x)`：将元素 `x` 插入队列
- `pop()`：移除并返回队列中优先级最高的元素
- `top()`：返回队列中优先级最高的元素

基于堆的优先队列是一种使用堆数据结构实现的优先队列。堆是一种完全二叉树，其中每个节点的键值都大于或等于其子节点的键值。

基于堆的优先队列的实现如下：

class PriorityQueue:
    def __init__(self):
        sel