编辑“︁C++ 堆操作”︁

= C++堆操作 =

== 介绍 ==
在C++中，'''堆操作'''（Heap Operations）是指使用标准模板库（STL）提供的算法来管理堆数据结构的一系列操作。堆是一种特殊的二叉树结构，通常分为'''最大堆'''（Max Heap）和'''最小堆'''（Min Heap）。在最大堆中，父节点的值总是大于或等于子节点的值；而在最小堆中，父节点的值总是小于或等于子节点的值。

C++ STL提供了以下主要堆操作函数：
* <code>std::make_heap</code>：将普通序列转换为堆结构。
* <code>std::push_heap</code>：向堆中插入元素并保持堆性质。
* <code>std::pop_heap</code>：移除堆顶元素并保持堆性质。
* <code>std::sort_heap</code>：将堆转换为有序序列。

堆操作在优先队列、排序算法和动态数据管理中有广泛应用。

== 堆的基本性质 ==
堆是一个完全二叉树，可以用数组或向量高效表示。对于索引为 <math>i</math> 的节点：
* 父节点索引：<math>\left\lfloor \frac{i-1}{2} \right\rfloor</math>
* 左子节点索引：<math>2i + 1</math>
* 右子节点索引：<math>2i + 2</math>

<mermaid>
graph TD
    A[10] --> B[9]
    A --> C[8]
    B --> D[7]
    B --> E[6]
    C --> F[5]
    C --> G[4]
</mermaid>

上图展示了一个最大堆的示例，其中每个父节点的值都大于其子节点。

== C++ STL堆操作函数 ==

=== std::make_heap ===
<code>std::make_heap</code> 将给定的范围（如向量或数组）转换为堆结构。

<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // 将向量转换为最大堆
    std::make_heap(v.begin(), v.end());
    
    // 输出堆顶元素（最大值）
    std::cout << "堆顶元素: " << v.front() << std::endl;
    
    return 0;
}
</syntaxhighlight>

'''输出：'''
<pre>
堆顶元素: 9
</pre>

=== std::push_heap ===
<code>std::push_heap</code> 用于向堆中插入新元素。注意：需要先将元素添加到容器末尾，再调用此函数。

<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {9, 5, 4, 1, 1, 3, 2, 6};
    std::make_heap(v.begin(), v.end());
    
    // 添加新元素
    v.push_back(8);
    
    // 重新调整堆
    std::push_heap(v.begin(), v.end());
    
    std::cout << "新堆顶元素: " << v.front() << std::endl;
    
    return 0;
}
</syntaxhighlight>

'''输出：'''
<pre>
新堆顶元素: 9
</pre>

=== std::pop_heap ===
<code>std::pop_heap</code> 将堆顶元素移动到容器末尾，并重新调整剩余元素为堆。

<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {9, 8, 4, 6, 5, 3, 2, 1};
    std::make_heap(v.begin(), v.end());
    
    // 移除堆顶元素
    std::pop_heap(v.begin(), v.end());
    v.pop_back();
    
    std::cout << "移除后堆顶元素: " << v.front() << std::endl;
    
    return 0;
}
</syntaxhighlight>

'''输出：'''
<pre>
移除后堆顶元素: 8
</pre>

=== std::sort_heap ===
<code>std::sort_heap</code> 将堆转换为有序序列（升序或降序）。

<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {9, 5, 4, 1, 1, 3, 2, 6};
    std::make_heap(v.begin(), v.end());
    
    // 将堆排序为升序
    std::sort_heap(v.begin(), v.end());
    
    std::cout << "排序后: ";
    for (int num : v) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}
</syntaxhighlight>

'''输出：'''
<pre>
排序后: 1 1 2 3 4 5 6 9
</pre>

== 实际应用案例 ==

=== 优先队列实现 ===
堆常用于实现优先队列（Priority Queue），C++中可以直接使用 <code>std::priority_queue</code>，但其底层也是基于堆操作。

<syntaxhighlight lang="cpp">
#include <iostream>
#include <queue>

int main() {
    // 默认是最大堆
    std::priority_queue<int> pq;
    
    pq.push(30);
    pq.push(10);
    pq.push(20);
    
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    
    return 0;
}
</syntaxhighlight>

'''输出：'''
<pre>
30 20 10
</pre>

=== Top K 问题 ===
堆操作可以高效解决Top K问题（找出前K个最大或最小的元素）。

<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>
#include <algorithm>

void findTopK(std::vector<int>& nums, int k) {
    std::make_heap(nums.begin(), nums.end());
    
    std::cout << "Top " << k << " elements: ";
    for (int i = 0; i < k; ++i) {
        std::pop_heap(nums.begin(), nums.end() - i);
        std::cout << nums[nums.size() - 1 - i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
    findTopK(nums, 3);
    
    return 0;
}
</syntaxhighlight>

'''输出：'''
<pre>
Top 3 elements: 9 6 5
</pre>

== 性能分析 ==
堆操作的时间复杂度如下：
* <code>std::make_heap</code>：<math>O(n)</math>
* <code>std::push_heap</code> 和 <code>std::pop_heap</code>：<math>O(\log n)</math>
* <code>std::sort_heap</code>：<math>O(n \log n)</math>

== 总结 ==
C++ STL提供的堆操作函数使得堆数据结构的管理变得简单高效。通过合理使用这些函数，可以轻松实现优先队列、排序和Top K等常见算法问题。对于初学者来说，理解堆的基本性质和STL接口是掌握这一概念的关键。

[[Category:编程语言]]
[[Category:C++]]
[[Category:C++stl 算法]]