本文主要是介绍C++语言基础 —— STL —— 容器与迭代器 —— heap，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【概述】
在 STL 中，并没有将堆作为一种容器，其实现需要借助更低一层的容器组件作为其底层机制，比如：list、priority_queue 等，heap 的底层机制 vector 本身就是一个类模板，heap 基于 vector 便实现了对各种数据类型的操作。
heap 是一个类属算法，其包含在头文件 <algorithm> 中，在 STL 中，heap 被默认调整成为小根堆，但可以通过自定义 cmp() 函数实现所需的大根堆或小根堆。
【操作】
在 STL 中，常用的堆操作有以下 4 个：
- make_heap(first,end,cmp())：将这范围 [first,end) 的数组或向量建成一个堆，在第三个参数缺省时，默认为大根堆
- pop_heap(first,end,cmp())：将最大/最小的元素从堆中弹出，其本质并非真的将最大最小的元素弹出，而是根据 cmp() 函数重新排序堆，只是将 first 与 end 交换，并将范围由 [first,end) 改为 [first,end-1)
- push_heap(first,end,cmp())：假设范围 [first,end-1) 是一个有效的堆，然后将新元素加进来，根据 cmp() 函数构建一个新堆
- sort_heap(first,end,cmp())：对范围 [first,end) 的序列根据 cmp() 重新排序，相应的，其破坏了堆的结构
bool cmp(int a,int b){return a>b;
}
int main(){int number[20]={29,23,20,22,17,15,26,51,19,12,35,40};//结果是:51 35 40 23 29 20 26 22 19 12 17 15make_heap(&number[0],&number[12]);for(int i=0;i<12;i++)printf("%d ",number[i]);printf("\n");//结果是：12 17 15 19 23 20 26 51 22 29 35 40make_heap(&number[0],&number[12],cmp);for(int i=0;i<12;i++)printf("%d ",number[i]);printf("\n");//结果是：8 17 12 19 23 15 26 51 22 35 40 20number[12]=8;//加入元素8push_heap(&number[0],&number[13],cmp);//加入后调整for(int i=0;i<13;i++)printf("%d ",number[i]);printf("\n");//结果是：12 17 15 19 23 20 26 51 22 29 35 40pop_heap(&number[0],&number[13],cmp);//弹出元素8for(int i=0;i<12;i++)printf("%d ",number[i]);printf("\n");//结果是：51 40 35 29 26 23 22 20 19 17 15 12sort_heap(&number[0],&number[12],cmp);for(int i=0;i<12;i++)printf("%d ",number[i]);printf("\n");return 0;
}
这篇关于C++语言基础 —— STL —— 容器与迭代器 —— heap的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
