Chinaunix首页 | 论坛 | 博客
  • 博客访问: 485986
  • 博文数量: 80
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1916
  • 用 户 组: 普通用户
  • 注册时间: 2013-07-11 22:01
个人简介

从事实时计算多年,熟悉jstorm/spark/flink/kafka/rocketMq, 热衷于开源,希望在这里和前辈们一起学习与分享,得到长足的进步!邮箱:hustfxj@gmail.com 我的githup地址是:https://github.com/hustfxj。欢迎和大家一起交流探讨问题。

文章分类

全部博文(80)

文章存档

2017年(11)

2015年(3)

2014年(33)

2013年(33)

分类: C/C++

2014-03-06 20:37:44

sort  是按照给定的 排序规则排序,比如从小到大,或从大到小
make_heap 是按照给定的排序准则,把“最大”的元素排列到首位,而其他元素看上去并非有序:比如对序列  3 4 5 6 7 5 6 7 8 9 1 2 3 4  用make_heap 排序后为:9 8 6 7 7 5 5 3 6 4 1 2 3 4    如果你把这些元素转换为二叉,就可以看出来每个节点的值都小于或等于其父节点值,此外heap 算法能够保证在对数时间内增加或移除一个元素;是实做的理想结构

 

下面再介绍STL中与堆相关的4个函数——建立堆make_heap(),在堆中添加数据push_heap(),在堆中删除数据pop_heap()和堆排序sort_heap():

头文件 #include

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

建立堆

make_heap(_First, _Last, _Comp)

默认是建立最大堆的。对int类型,可以在第三个参数传入greater()得到最小堆。当然这里也可以是普通函数,返回值是bool

 

在堆中添加数据

push_heap (_First, _Last)

要先在容器中加入数据,再调用push_heap ()

 

在堆中删除数据

pop_heap(_First, _Last)

要先调用pop_heap()再在容器中删除数据

 

堆排序

sort_heap(_First, _Last)

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

点击(此处)折叠或打开

  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.     //动态申请vector 并对vector建堆
  21.     vector<int> *pvet = new vector<int>(40);
  22.     pvet->assign(a, a + MAXN);

  23.     //建堆
  24.     make_heap(pvet->begin(), pvet->end());
  25.     PrintfVectorInt(*pvet);

  26.     //加入新数据 先在容器中加入,再调用push_heap()
  27.     pvet->push_back(25);
  28.     push_heap(pvet->begin(), pvet->end());
  29.     PrintfVectorInt(*pvet);

  30.     //删除数据 要先调用pop_heap(),再在容器中删除
  31.     pop_heap(pvet->begin(), pvet->end());
  32.     pvet->pop_back();
  33.     pop_heap(pvet->begin(), pvet->end());
  34.     pvet->pop_back();
  35.     PrintfVectorInt(*pvet);

  36.     //堆排序
  37.     sort_heap(pvet->begin(), pvet->end());
  38.     PrintfVectorInt(*pvet);

  39.     delete pvet;
  40.     return 0;
  41. }

当然也可以以数组作为底层结构

点击(此处)折叠或打开

  1. #include<algorithm>

  2. #include<cstdio>

  3. using namespace std;

  4. bool cmp(int a,int b)

  5. {

  6.     return a>b;

  7. }

  8. int main()

  9. {

  10.     int i,number[20]={29,23,20,22,17,15,26,51,19,12,35,40};

  11.     make_heap(&number[0],&number[12]);

  12.     //结果是:51 35 40 23 29 20 26 22 19 12 17 15

  13.     for(i=0;i<12;i++)

  14.         printf("%d ",number[i]);

  15.     printf("\n");

  16.     make_heap(&number[0],&number[12],cmp);

  17.     //结果:12 17 15 19 23 20 26 51 22 29 35 40

  18.     for(i=0;i<12;i++)

  19.         printf("%d ",number[i]);

  20.     printf("\n");

  21.     //加入元素8

  22.     number[12]=8;

  23.     //加入后调整

  24.     push_heap(&number[0],&number[13],cmp);

  25.     //结果:8 17 12 19 23 15 26 51 22 35 40 20

  26.     for(i=0;i<13;i++)

  27.         printf("%d ",number[i]);

  28.     printf("\n");

  29.     //弹出元素8

  30.     pop_heap(&number[0],&number[13],cmp);

  31.     //结果:12 17 15 19 23 20 26 51 22 29 35 40

  32.     for(i=0;i<13;i++)

  33.         printf("%d ",number[i]);

  34.     printf("\n");

  35.     sort_heap(&number[0],&number[12],cmp);

  36.     //结果不用说都知道是有序的了!

  37.     for(i=0;i<12;i++)

  38.         printf("%d ",number[i]);

  39.     return 0;

  40. }
一些就是其他地方copy过来的,个人感觉写的很不错

heap能够用来排序,其调整大顶堆或小顶堆的方法能够作为priority queue实现的低层机制,但细看了《STL源码剖析》中的有关Heap一节,才知道STL中并没有把heap作为一种容器组件,heap的实现亦需要更低一层的容器组件(诸如list,array,vector)作为其底层机制。Heap是一个类属算法,包含在algorithm头文件中。

         在《数据结构》的课时学习中,我们知道heap的图其实是一颗完全二叉树,基于其特征,可以用array来存储,且根据其需要,分为大顶堆和小顶堆。然而,在STL中,由于array的缺点(无法动态改变大小),改用vector代替array,并且只供应大顶堆max-heap

         在此又不得不粗略提一下vector容器的实现原理。

Vector容器的数据结构实际就是一段线性连续空间,用迭代器startfinish分别指向连续空间中目前被使用的范围(就好像队列queue的头尾指针一样),就个人认为vector其实是和array几乎一样的存在。但vector为了实现快速的内存分配,在分配空间容量时会比当前所需空间多一些,用于存放新添加的元素;当预留空间用完时,以加倍当前容量的分配策略实现重新分配(事实上容量的重新分配需要“重新配置、元素移动、释放原空间”的过程,事实证明这个策略所变现出来的性能非常好)。然后,在基于array和快速内存分配的基础上,应用了迭代器beginendend_of_storage(连续可用空间的尾),提供了首尾标示、大小、容量、空容器、标注([ ])运算等等的机能。

         STL中为堆heap的创建和操作提供了4种算法:make_heappop_heappush_heapsort_heap。其中:

         make_heap:利用区间[first,last)中的元素构造一个heap

                    函数原型:void make_heap(first,last)

                    void make_heap(first,last ,compare_fuction)

         pop_heap:  假定区间[first,last)中已包含一个堆,将first位置和last-1位置上的值交换,重新[first,last-1)调整为一个堆。

    函数原型:void pop_heap(first,last);

              void pop_heap(first,last,compare_fuction)

         push_heap: 假定区间[first,last-1)已经包含了一个堆,把区间[first,last)调整为一个堆(从而     把last-1位置上的元素压入堆。

    函数原型:void push_heap(first,last);

              void push_heap(first,last,compare_fuction).

         sort_heap: 对存储在堆中的元素进行排序。

                    函数原型:void sort_heap(first,last);

                              void sort_heap(first,last,compare_fuction)

         对比之前做过的堆排序的实验,感觉STL中的heap优化并不比教材里面介绍的强多少。想想也应该是,那算法思想是一模一样的,但在代码的实现上,STL中做到了规范化。其次,STL中应用了vector作为heap的底层机制,克服了教材中用array存储空间无法动态改变大小的缺点。其三,STL中关于heap的四个算法都实现了函数重载,虽然STL中关于heap默认调整成的是大顶堆,但却可以让用户利用自定义的compare_fuction函数实现大顶堆或小顶堆。其四,heap的低层机制vector本身就是一个类模板,heap基于vector便实现了对各种数据类型(无论基本数据类型还是用户自定义的数据类型)的堆排(前提是用户自定义的数据类型要提供比较机制compare_fuction函数)。


 

阅读(2693) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~