C++ 堆

2025年5月23日 | 阅读 11 分钟

在 C++ 中，堆是一种主要用于优先队列和高效检索最大或最小元素的树形数据结构。C++ STL 提供了许多用于堆操作的内置函数，例如 make_heap()、push_heap()、pop_heap()、sort_heap()、is_heap 和 is_heap_until()。

堆也称为自由存储区，它指的是程序运行时用于动态分配的内存区域。使用 new 或 malloc() 运算符时，内存会从该区域分配。如果我们使用最新的 new 或 malloc() 运算符，内存将从该部分获取。

C++ 中的堆类型

在 C++ 中，堆主要可分为两种类型。

最大堆 (Max-Heap)
最小堆 (Min-Heap)

有时，这些堆通常应用于各种算法，例如优先队列、排序算法和其他图算法。此库的功能包括与堆相关的函数，但可以根据比较器将其设置为充当最小堆或最大堆。

最大堆 (Max-Heap)

在 C++ 中，最大堆 (Max-Heap) 是一种二叉堆，其中任何节点的键都大于或等于其子节点的键。换句话说，最大的元素位于根节点，并且最大堆的所有子树也遵循最大堆属性。

最大堆的特性

C++ 中最大堆的几个特性如下：

由于堆数据结构保持父节点键大于子节点键的属性，因此最大元素位于堆的顶部。
换句话说，对于二叉树中的每个父节点，其值都大于或等于其任何子节点的值。
堆的构建方式是为了在不违反堆属性的情况下包含新元素。

最大堆的用例

C++ 中最大堆的几个用例如下：

优先队列：与二叉搜索树不同，最大堆中同一级别的节点未排序。另一方面，根节点始终包含最大堆中优先级最高的节点。因此，在许多使用优先队列的应用中都实现了最大堆。
堆排序：在此结构中，数据按降序排列，并使用最大堆。该数组通过不断删除堆中最大的元素并将其放在数组末尾来对给定数组进行排序。

C++ 最大堆示例

让我们举一个例子来说明 C++ 中的最大堆。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  //using standard namespace

int main() {  //Main function
    
    vector<int> data = {10, 20, 15, 30, 40};
    // Creating a max-heap
    make_heap(data.begin(), data.end());
    cout << "Max Heap: ";   //prints the max heap value
    for (int n : data) cout << n << " ";   
    return 0;
}

编译并运行

输出

Max Heap: 40 30 15 10 20

说明

在此示例中，我们演示了如何使用 STL 的 make_heap() 函数创建最大堆。它初始化一个包含元素的向量，将其转换为最大堆（其中最大元素位于前面），然后打印已堆化的向量。

最小堆 (Min-Heap)

在 C++ 中，最小堆 (Min-Heap) 是一个项的集合，它与二叉堆具有相似的属性，但遵循任何父节点键小于或等于其子节点键的条件。它确保最小的元素始终位于堆的根节点。此外，最小堆中的每个子树也必须满足此属性，这使其可用于多种操作，包括检索或删除最小元素。

最小堆的特性

C++ 中最小堆的几个特性如下：

在堆中，最小的元素是位于该堆根节点或堆顶部的元素。
还表明，每个父节点都小于或等于其子节点集中的节点。
堆的组织方式使得在插入新项时能够保持堆属性。

用例

C++ 中最小堆的几个用例如下：

优先队列：最小堆的第一个节点将始终具有最低优先级。因此，它们用于优先队列，其中必须移除优先级最低的元素。
Dijkstra 算法：在两种堆实现中，最小堆在 Dijkstra 的最短路径等图算法中非常有用，在这些算法中，我们需要在每一步中找到最小（成本最低）的节点。

C++ 最小堆示例

为了在 C++ 中使用最小堆，我们可以使用一个自定义比较器来定义顺序。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  //using standard namespace
int main() {   //main function
    
    vector<int> data = {10, 20, 15, 30, 40};    
    // Creating a min-heap using a custom comparator
    make_heap(data.begin(), data.end(), greater<int>());
    cout << "Min Heap: ";
    for (int n : data) cout << n << " ";
    return 0;
}

编译并运行

输出

Min Heap: 10 20 15 30 40

说明

在此示例中，我们使用 greater<int>() 比较器通过 make_heap() 从向量创建了一个最小堆，该比较器可确保最小元素位于堆的前面。之后，按堆结构顺序打印元素。

我们为什么要使用 C++ 中的堆？

以下是我们使用 C++ 中堆的一些原因。

1) 动态大小

这意味着，当对象或数组的大小在编译时无法确定时，堆会根据用户输入或其他条件来分配内存。

2) 更长的生命周期

在 C++ 中，堆内存一直被使用，直到被显式释放。当对象需要比创建它们的函数更长的生命周期时，这一点尤其有用。

3) 灵活的数据结构

单向链表、树、图和哈希表以及其他复杂的数据结构由于其动态性都需要堆分配。

4) 有效利用内存

堆内存用于处理大数据并克服栈溢出情况，尤其是在递归算法或大型数据集的情况下。

C++ STL 中的堆函数

下表显示了 C++ STL 中的不同函数。它们如下：

make_heap()	将一个范围转换为最大堆
push_heap()	将元素插入堆并保持顺序
pop_heap()	移除最大元素并保持堆顺序
sort_heap()	将堆排序为升序
is_heap()	检查一个范围是否为有效堆
is_heap_until()	查找堆属性被违反的点

C++ STL 中的堆操作

C++ STL 中有几种堆操作。其中一些操作如下：

1) make_heap() - 将向量转换为堆

在 C++ 中，make_heap() 函数用于将给定范围转换为堆。默认情况下，它会创建一个最大堆，其中最大元素位于范围的前面。

语法

它具有以下语法：

在此语法中，提供的迭代器应为 randomAccessIterator 类型。

C++ make_heap() 示例

让我们举一个例子来说明 C++ 中的 make_heap() 函数。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  //using standard namespace
int main() {  //Main Function
    vector<int> v = {10, 30, 20, 5, 1};
    make_heap(v.begin(), v.end());
    cout << "Max heap: ";
    for (int i: v)
        cout << i << " ";
    return 0;
}

编译并运行

输出

Max heap: 30 10 20 5 1

说明

在此示例中，我们使用了 make_heap() 函数，该函数可以排列元素，使最大值位于向量的前面。之后，它打印向量的堆结构化内容。

2) push_heap() - 向堆添加新元素

在 C++ 中，push_heap() 函数用于插入一个新元素，同时保持堆的顺序。

语法

它具有以下语法：

C++ push_heap 示例

让我们举一个例子来说明 C++ 中的 push_heap() 函数。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  //using standard namespace
int main() {   //Main Function
    vector<int> v = {10, 20, 30};
    make_heap(v.begin(), v.end());
    v.push_back(25);
    push_heap(v.begin(), v.end());
    cout << "After push_heap: ";
    for (int i: v)
        cout << i << " ";
    return 0;
}

编译并运行

输出

After push_heap: 30 25 10 20

说明

在此示例中，我们使用 make_heap() 函数将向量转换为堆。之后，使用 push_back() 添加一个新元素 (25)，并调用 push_heap() 来维护堆属性。

3) pop_heap() - 移除根 (最大元素)

在 C++ 中，pop_heap() 函数用于将堆的最大元素移动到范围的末尾并恢复堆的顺序。

语法

它具有以下语法：

C++ pop_heap() 示例

让我们举一个例子来说明 C++ 中的 pop_heap() 函数。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  //using standard namespace
int main() {   //Main Function
    vector<int> v = {50, 40, 30, 20, 10};
    make_heap(v.begin(), v.end());
    pop_heap(v.begin(), v.end());
    v.pop_back(); // Remove max
    cout << "After pop_heap: ";
    for (int i: v)
        cout << i << " ";
    return 0;
}

编译并运行

输出

After pop_heap: 40 20 30 10

说明

在此示例中，我们使用 make_heap() 函数将向量 v 组织成一个最大堆。之后，pop_heap() 函数将最大元素（堆的根）移动到向量的末尾。v.pop_back() 函数从容器中移除最大元素。

4) sort_heap() - 将堆转换为排序数组

在 C++ 中，sort_heap() 函数用于将堆转换为升序排序的范围。

语法

它具有以下语法：

C++ sort_heap() 示例

让我们举一个例子来说明 C++ 中的 sort_heap() 函数。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  //using standard namespace
int main() {  //Main function
    vector<int> v = {20, 10, 30, 5, 1};
    make_heap(v.begin(), v.end());
    sort_heap(v.begin(), v.end());
    cout << "Sorted: ";   //print the sorted heap
    for (int i: v)
        cout << i << " ";
    return 0;
}

编译并运行

输出

Sorted: 1 5 10 20 30

说明

在此示例中，我们使用 make_heap() 函数将向量 v 重排为最大堆。之后，sort_heap() 函数通过反复将最大元素移到末尾并减小堆大小来将堆排序为升序。

5) is_heap() - 检查范围是否为堆

在 C++ 中，is_heap() 函数用于检查提供的范围是否为堆。如果范围是有效堆，则返回 true；否则返回 false。

语法

它具有以下语法：

C++ is-heap 示例

让我们举一个例子来说明 C++ 中的 is_heap 函数。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  //using standard namespace
int main() {   //Main Function
    vector<int> v = {30, 20, 10};
    if (is_heap(v.begin(), v.end()))
        cout << "This is a heap." << endl;
    else
        cout << "Not a heap." << endl;
    return 0;
}

编译并运行

输出

This is a heap.

说明

在此示例中，我们取向量 {30, 20, 10}，它是一个有效的最大堆，因为每个父节点都大于或等于其子节点。is_heap(v.begin(), v.end()) 函数返回 true，因此程序打印“这是一个堆”。

6) is_heap_until() - 检查直到不再是堆为止

在 C++ 中，is_heap_until() 返回一个指向第一个违反堆属性的元素的迭代器。

语法

它具有以下语法：

C++ is_heap_until() 示例

让我们举一个例子来说明 C++ 中的 is_heap_until() 函数。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector<int> v = {40, 30, 20, 10, 5, 100};
    auto it = is_heap_until(v.begin(), v.end());
    cout << "Heap until index: " << distance(v.begin(), it) << endl;
    return 0;
}

编译并运行

输出

Heap until index: 5

说明

在此示例中，我们使用 is_heap_until() 函数来确定从向量开头有多少个元素保持堆属性。它打印最大堆结构首次被违反的索引。

C++ 堆示例

让我们来看一个 C++ 程序来演示 C++ STL 中堆的概念，包括 make_heap()、push_heap()、pop_heap()、sort_heap()、is_heap、is_heap_until()。

示例

#include<bits/stdc++.h>  
using namespace std;  
int main()    //Main function
{     
              // create a vector
      vector<int> v1 = {2540, 6650, 4460, 2665, 9915};      
    // function make_heap()    
    make_heap(v1.begin(), v1.end());  
    //using heap function
    cout << "highest element in the heap created by us is: ";  
    cout << v1.front() << endl;        
    // using the push_back() function
    v1.push_back(50);  
    // using push_heap() function 
    push_heap(v1.begin(), v1.end());   
    cout << "highest element in a heap after operating is: ";  
    cout << v1.front() << endl;  
    // using pop_heap() function
    pop_heap(v1.begin(), v1.end());  
    v1.pop_back();  
          //using heap function
    cout << "highest element in a heap after performing the pop operation is: ";  
    cout << v1.front() << endl;  
    return 0;  
}  

编译并运行

输出

the highest element in a heap created by us is 9915
the highest element in a heap after operating is 9915
the highest element in a heap after performing the pop operation is 6650

说明

在此示例中，我们首先使用 make_heap() 创建一个最大堆，然后使用 push_back() 和 push_heap() 添加一个新元素，最后使用 pop_heap() 和 pop_back() 移除最大元素。

复杂度分析

向堆中插入元素

时间复杂度：O(log n)

最小堆：如果元素小于其父节点，则可能需要将其向上移动（以确保最小元素位于根节点）。
最大堆：如果元素大于其父节点，则可能需要将其向上移动（以确保最大元素位于根节点）。

从堆中删除元素

时间复杂度：O(log n)

最小堆：如果元素大于其一个或两个子节点，则可能需要将其向下移动（以确保最小元素位于根节点）。
最大堆：如果元素小于其一个或两个子节点，则可能需要将其向下移动（以确保最大元素位于根节点）。

结论

总之，C++ STL 中的堆提供了一种强大而标准化的方法，通过将标准容器（如 vector）与 <algorithm> 头文件中的实用函数结合使用来管理基于优先级的数据。这些函数包括 make_heap()、push_heap()、pop_heap() 和 sort_heap()，它们有助于开发人员在不进行手动构建的情况下实现最大堆（或使用自定义比较器实现最小堆）。

C++ 堆选择题

1) 在 C++ STL 的上下文中，什么是堆？

自平衡二叉搜索树
满足堆属性的完全二叉树
带有排序节点的链表
成员未排序的树。

答案：b) 满足堆属性的完全二叉树

2) 堆属性在最大堆中确保了什么？

第一个条件是每个父节点的值必须小于其子节点的值。
对于树中的所有父节点，它们的值都高于其子节点的值。
树是不平衡的
每一行或每一列的所有给定元素集都按递增顺序排列。

答案：b) 对于树中的所有父节点，它们的值都高于其子节点的值。

3) push_heap() 函数做什么？

从头开始创建新堆
将给定元素附加到数组，并检查相应数组的排序。
在插入后重新排序容器以保持堆属性
从最小堆中移除最小元素

答案：c) 在插入后重新排序容器以保持堆属性

4) 在容器上调用 pop_heap() 之前必须满足什么条件？

容器必须已排序
容器必须是有效的堆
容器必须为空
容器必须是反转的

答案：b) 容器必须是有效的堆

5) 选择堆在 C++ 中的错误用例

优先队列实现
在最大堆中以恒定时间查找最小元素的能力
按升序排列数据
优先处理动态任务并高效管理活动

答案：b) 在最大堆中以恒定时间查找最小元素的能力

下一主题'void*' 在 C 和 C++ 中有何不同

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 堆

C++ 中的堆类型

最大堆 (Max-Heap)

最大堆的特性

最大堆的用例

C++ 最大堆示例

示例

最小堆 (Min-Heap)

最小堆的特性

用例

C++ 最小堆示例

示例

我们为什么要使用 C++ 中的堆？

C++ STL 中的堆函数

C++ STL 中的堆操作

1) make_heap() - 将向量转换为堆

C++ make_heap() 示例

示例

2) push_heap() - 向堆添加新元素

C++ push_heap 示例

示例

3) pop_heap() - 移除根 (最大元素)