【概述】
在 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;}