C++ 堆操作

C++堆操作

介绍

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

C++ STL提供了以下主要堆操作函数：

• std::make_heap：将普通序列转换为堆结构。
• std::push_heap：向堆中插入元素并保持堆性质。
• std::pop_heap：移除堆顶元素并保持堆性质。
• std::sort_heap：将堆转换为有序序列。

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

堆的基本性质

堆是一个完全二叉树，可以用数组或向量高效表示。对于索引为 $i$ 的节点：

• 父节点索引：$\lfloor \frac{i-1}{2}\rfloor$
• 左子节点索引：$2i+1$
• 右子节点索引：$2i+2$

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

C++ STL堆操作函数

std::make_heap

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

#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;
}

输出：

堆顶元素: 9

std::push_heap

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

#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;
}

输出：

新堆顶元素: 9

std::pop_heap

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

#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;
}

输出：

移除后堆顶元素: 8

std::sort_heap

std::sort_heap 将堆转换为有序序列（升序或降序）。

#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;
}

输出：

排序后: 1 1 2 3 4 5 6 9

实际应用案例

优先队列实现

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

#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;
}

输出：

30 20 10

Top K 问题

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

#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;
}

输出：

Top 3 elements: 9 6 5

性能分析

堆操作的时间复杂度如下：

• std::make_heap：$O(n)$
• std::push_heap 和 std::pop_heap：$O(\log n)$
• std::sort_heap：$O(n\log n)$

总结

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