%%
# 纲要
> 主干纲要、Hint/线索/路标
# Q&A
#### 已明确
#### 待明确
> 当下仍存有的疑惑
**❓<font color="#c0504d"> 有什么问题？</font>**
# Buffer
## 闪念
> sudden idea
## 候选资料
> Read it later
%%
# 优先队列
「**优先队列（priority queue）**」是一种**抽象数据结构**，定义为**具有==优先级排序==的队列**，每次出队的是**队列中优先级最高的元素**。
优先队列的具体实现可以是：**二叉堆**、**斐波那契堆**等。
「**二叉堆**」通常用于**实现优先队列**：
- "**大顶堆**" 相当于按 **==从大到小== 顺序出队的优先队列（"元素==大==的优先级高"）**
- "**小顶堆**" 相当于按 **==从小到大== 顺序出队的优先队列（"元素==小==的优先级高"）**
<br>
# 堆的定义（二叉堆）
从**逻辑**上来说，「**==堆（heap）==**」被定义为一种**满足特定条件**的 **==完全二叉树==**，分为**两种类型**：
- 「**大顶堆（max heap）**」：**完全二叉树**上**每个节点的值都 `>=` 其子节点的值**。
- 「**小顶堆（min heap）**」： **完全二叉树**上**每个节点的值都 `<=` 其子节点的值**。
**大顶堆**中，**根节点为树上的==最大值==**； **小顶堆**中，**根节点为树上的==最小值==**
![[_attachment/00-数据结构与算法笔记/数据结构/堆（二叉堆）.assets/IMG-堆（二叉堆）-54BC0BD3A4A8EB8209AB3D99EBA3260C.png|660]]
<br>
# 堆的存储实现
堆的 "**逻辑结构**" 是 "**==完全二叉树==**"，其**底层数据结构**通常为 "**==数组==**"，
**堆**按 **==层序遍历==** 依次存放于数组中：
- **首项**元素 `arr[0]` 为**堆顶/树根**；
- 给定**任意节点下标 $i$**：
- 其 **父节点下标**为 $\Large \left\lfloor\frac{i-1}{2}\right\rfloor$ ；
- 其**左孩子节点下标**为 $2i+1$，**右孩子节点下标**为 $2i+2$。
- **最后一个节点 `arr[n-1]`** 的**父节点**即为 "**最后一个内部节点**"。
![[_attachment/00-数据结构与算法笔记/数据结构/堆（二叉堆）.assets/IMG-堆（二叉堆）-6A1E7AEAB289B16A53902D7C027D58C7.png|751]]
# 堆的相关操作
两个**最基本的底层操作**（以**大顶堆**为例）：
- **上滤 `SiftUp`**：**给定==叶节点== $i$，若其大于父节点，则与父节点交换，持续地上移**；
- **下滤 `SiftDown`**：**给定==内部节点== $i$，若其小于子节点，则与最小子节点交换，持续地下移**。
基于上述操作所实现的**堆的外部接口**：
- **==`HeapPush` 入堆==**： 将元素追加到**列表尾**，**执行上滤 `SiftUp`**。
- **==`HeapPop` 出堆==**： 将**堆顶根节点**交换到**列表尾**并`pop`，**对新的根节点执行下滤 `SiftDown`**。
- **==`Heapify` 堆化==**：从**最后一个内部节点**开始直至**根节点**，依次执行`SiftDown `建堆 (**==自底向上==建堆**)
- **==`Heapsort` 堆排序==**：将**堆顶元素**与**尾部元素**交换并**将尾部元素视作排除与堆外**，**对新的根节点执行下滤`SiftDown`**
其中，**只有 `HeapPush` 基于上滤 `Siftup` 操作**，**其余三项均只基于下滤 `SiftDown` 操作**。
`heapsort`与 `heappop` 的思路一样, 将旧根交换到尾部再对新根执行`sift_down`, 只不过 `heapsort` 是**通过减小`size`变量收缩堆的边界来模拟缩减尾部**, 而 `heappop`是真的移除尾部元素。
### 堆的操作效率
| 操作 | 说明 | 时间复杂度 |
| ----------- | ------------- | ----------- |
| `push()` | 元素入堆 | $O(\log n)$ |
| `pop()` | 弹出堆顶元素 | $O(\log n)$ |
| `top()` | 获取堆顶元素 | $O(1)$ |
| `heapify()` | 建堆/堆化（自底向上建堆） | $O(n)$ |
<br>
## （1）建堆
两种方式：
- **自顶向下建堆**：依次调用 `HeapPush` 将所有元素入堆，时间复杂度为 $O(n\log n)$；
- **自底向上建堆**：调用 `Heapify` 完成建堆——**从底向上，对每个==内部结点==进行下滤操作，直至根节点**，时间复杂度为 $O(n)$
#### "自底向上" 建堆的实现
```cpp
// 自底向上堆化
// 堆化所有内部节点(堆对应的逻辑结构为完全二叉树, 数组中元素等同于按层序遍历得到, 所以最后一个父结点及之前全都是内部结点)
void MaxHeap::Heapify() {
if (arr.empty()) throw std::runtime_error("empty heap");
int last_parent = (arr.size() - 1) / 2; // 最后一个父节点, 也即最后一个内部节点.
for (int i = last_parent; i >= 0; --i) {
SiftDown(i);
}
}
```
#### "自底向上" 建堆的时间复杂度分析
`Heapify` 的时间复杂度为 $O(n)$。
![[_attachment/00-数据结构与算法笔记/数据结构/堆（二叉堆）.assets/IMG-堆（二叉堆）-538BC4C0B2F46EE7BE86795153D92F44.png|575]]
![[_attachment/00-数据结构与算法笔记/数据结构/堆（二叉堆）.assets/IMG-堆（二叉堆）-F35231FDCB5172FFA3401DB610054F70.png|600]]
## （2）入堆
入堆 `HeapPush`： 将元素追加到**列表尾**，**执行上滤 `SiftUp`**。
![[_attachment/00-数据结构与算法笔记/数据结构/堆（二叉堆）.assets/IMG-堆（二叉堆）-049525AF9D608BB2ADAA1CE7719F83BD.png]]
## （3）出堆
出堆 `HeapPop`： 将**堆顶根节点**交换到**列表尾**并`pop`，**对新的根节点执行下滤 `SiftDown`**。
![[_attachment/00-数据结构与算法笔记/数据结构/堆（二叉堆）.assets/IMG-堆（二叉堆）-602A768C2FD89917D4BF090B1CF95546.png]]
<br>
# 堆的完整实现
```cpp
// 大顶堆.
class MaxHeap {
public:
explicit MaxHeap(const vector<int>& arr) {
this->arr_ = arr;
heapify();
}
void push(int val) {
arr_.push_back(val);
siftUp(arr_.size() - 1);
}
void pop() {
if (arr_.empty()) throw std::runtime_error("empty heap");
swap(arr_[0], arr_.back());
arr_.pop_back();
siftDown(0);
}
int top() {
if (arr_.empty()) throw std::runtime_error("empty heap");
return arr_[0];
}
// 自底向上堆化
void heapify() {
if (arr_.empty()) return;
int last_leaf = arr_.size() - 1;
int last_internal = (last_leaf - 1) / 2;
for (int i = last_internal; i >= 0; --i) {
siftDown(i);
}
}
private:
// 上滤: 给定叶节点 i，若其大于父节点，则与父节点交换，持续地上移；
void siftUp(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (arr_[i] <= arr_[parent]) break;
swap(arr_[i], arr_[parent]);
i = parent;
}
}
// 下滤: 给定内部节点 i，若其小于子节点，则与最大子节点交换，持续地下移.
void siftDown(int i) {
while (true) {
int max_idx = i;
int left = 2*i + 1, right = 2*i + 2;
if (left < arr_.size() && arr_[left] > arr_[max_idx]) {
max_idx = left;
}
if (right < arr_.size() && arr_[right] > arr_[max_idx]) {
max_idx = right;
}
if (max_idx == i) break;
swap(arr_[max_idx], arr_[i]);
i = max_idx;
}
}
private:
vector<int> arr_;
};
```
<br><br>
# 堆排序
**==堆排序==** 是基于 "堆" 这一数据结构的排序方式，分为两步：
- **堆化**：调用 `heapify` 将原数组堆化，即**将数组元素按堆对应的逻辑方式进行排列**。
- **排序**：每次**将堆顶元素交换到 "剩余堆的末尾 i "**，将**末尾元素`i`从堆中排除**，并**对新的堆顶元素执行 `SiftDown` 下滤**。
整个过程相当于，**依次将==堆顶元素==弹出，==从后到前==地放置到数组之中，直至堆空**。
![[Excalidraw-Solution/堆.excalidraw.md#^group=YPf3kyOLhBHhMRMwP3Z3R|600]]
### 复杂度分析
- 时间复杂度：$O(n + n\log n)$ 堆化以及 n 项元素出堆的开销；
- 空间复杂度：$O(1)$ 堆排序无需额外的空间开销。
### 堆排序的实现
```cpp
// 堆排序(大顶堆进行升序排序)
class HeapSortImpl {
public:
static void sort(vector<int>& arr) {
int n = arr.size();
heapify(arr);
for (int i = n - 1; i > 0; --i) {
swap(arr[0], arr[i]); // 每次将堆顶元素交换到"剩余堆的末尾下标i"
siftDown(arr, 0, i); // 对新的堆顶元素进行下滤. 剩余堆的大小为i.
}
}
private:
static void heapify(vector<int>& arr) {
if (arr.empty()) return;
int last_leaf = arr.size() - 1;
int last_internal = (last_leaf - 1) / 2;
for (int i = last_internal; i >= 0; --i) {
siftDown(arr, i, arr.size());
}
}
static void siftDown(vector<int>& arr, int i, int size) {
while (true) {
int max_idx = i;
int left = 2*i + 1, right = 2*i + 2;
if (left < size && arr[left] > arr[max_idx]) {
max_idx = left;
}
if (right < size && arr[right] > arr[max_idx]) {
max_idx = right;
}
if (max_idx == i) break;
swap(arr[i], arr[max_idx]);
i = max_idx;
}
}
};
```
# 堆的作用
- **小顶堆**：求最大的 k 项元素（堆顶为第 k 大的元素，作为门槛）
- **大顶堆**：求最小的 k 项元素（堆顶为第 k 小的元素，作为门槛）
---
<br><br>
# C++ 标准库中的优先队列
> 由 `<queue>` 头文件提供
### `priority_queue` 类模版声明
> ![[_attachment/00-数据结构与算法笔记/数据结构/堆（二叉堆）.assets/IMG-堆（二叉堆）-BBF97F1EE9A07E34888331E9F63E9ADC.png|774]]
### 自定义比较函数
优先队列 `std::priority_queue` 以 `Compare(const T& a, const T& b)` 作为**比较函数**，
**当 ==`Compare(a, b)`== 为 `true` 时，认为 ==`b` 的优先级较高==**，从而**将 `b` 排在队列==前方==（靠近堆顶）**。
###### 例题
[[99-题解/leetcode/lc-692 前 K 个高频单词|lc-692 前 K 个高频单词]]
# C++ 标准库中的堆相关算法
> 由 `<algorithm>` 头文件提供
- `std::make_heap()`
- `std::push_heap()`
- `std::pop_heap()`
- `std::sort_heap()`
<br>
<br>
# 参考资料
[8.1 堆 - Hello 算法](https://www.hello-algo.com/chapter_heap/heap/)
# Footnotes