STL系列之四 heap 堆

系统管理员 2022-09-18 08:55 169阅读 0赞

原文地址：

[http://blog.csdn.net/morewindows/article/details/6967409][http_blog.csdn.net_morewindows_article_details_6967409]

下面再介绍STL中与堆相关的4个函数——建立堆make\_heap()，在堆中添加数据push\_heap()，在堆中删除数据pop\_heap()和堆排序sort\_heap()：

头文件 \#include <algorithm>

下面的\_First与\_Last为可以随机访问的迭代器（指针），\_Comp为比较函数（仿函数），其规则——如果函数的第一个参数小于第二个参数应返回true，否则返回false。

**建立堆**

make\_heap(\_First, \_Last, \_Comp)

默认是建立最大堆的。对int类型，可以在第三个参数传入greater<int>()得到最小堆。

** **

**在堆中添加数据**

push\_heap (\_First, \_Last)

要先在容器中加入数据，再调用push\_heap ()

**在堆中删除数据**

pop\_heap(\_First, \_Last)

要先调用pop\_heap()再在容器中删除数据

** **

**堆排序**

sort\_heap(\_First, \_Last)

排序之后就不再是一个合法的heap了

有关堆与堆排序的更详细介绍请参阅——《[白话经典算法系列之七 堆与堆排序][Link 1]》

下面给出STL中heap相关函数的使用范例：

**\[cpp\]**  [view plain][] [copy][view plain]

1.  //by MoreWindows( http://blog.csdn.net/MoreWindows )  
2.  \#include <cstdio>  
3.  \#include <vector>  
4.  \#include <algorithm>  
5.  \#include <functional>  
6.  **using** **namespace** std;  
7.  **void** PrintfVectorInt(vector<**int**> &vet)  
8.  \{  
9.      **for** (vector<**int**>::iterator pos = vet.begin(); pos != vet.end(); pos++)  
10.         printf("%d ", \*pos);  
11.     putchar('\\n');  
12. \}  
13. **int** main()  
14. \{  
15.     **const** **int** MAXN = 20;  
16.     **int** a\[MAXN\];  
17.     **int** i;  
18.     **for** (i = 0; i < MAXN; ++i)  
19.         a\[i\] = rand() % (MAXN \* 2);  
20.   
21.     //动态申请vector 并对vector建堆  
22.     vector<**int**> \*pvet = **new** vector<**int**>(40);  
23.     pvet->assign(a, a + MAXN);  
24.   
25.     //建堆  
26.     make\_heap(pvet->begin(), pvet->end());  
27.     PrintfVectorInt(\*pvet);  
28.   
29.     //加入新数据 先在容器中加入，再调用push\_heap()  
30.     pvet->push\_back(25);  
31.     push\_heap(pvet->begin(), pvet->end());  
32.     PrintfVectorInt(\*pvet);  
33.   
34.     //删除数据  要先调用pop\_heap()，再在容器中删除  
35.     pop\_heap(pvet->begin(), pvet->end());  
36.     pvet->pop\_back();  
37.     pop\_heap(pvet->begin(), pvet->end());  
38.     pvet->pop\_back();  
39.     PrintfVectorInt(\*pvet);  
40.   
41.     //堆排序  
42.     sort\_heap(pvet->begin(), pvet->end());  
43.     PrintfVectorInt(\*pvet);  
44.   
45.     **delete** pvet;  
46.     **return** 0;  
47. \}

[http_blog.csdn.net_morewindows_article_details_6967409]: http://blog.csdn.net/morewindows/article/details/6967409
[Link 1]: http://blog.csdn.net/morewindows/article/details/6709644
[view plain]: http://blog.csdn.net/morewindows/article/details/6967409#