关于stl的heap总结

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了

//by MoreWindows( http://blog.csdn.net/MoreWindows )
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
void PrintfVectorInt(vector<int> &vet)
{
    for (vector<int>::iterator pos = vet.begin(); pos != vet.end(); pos++)
        printf("%d ", *pos);
    putchar('\n');
}
int main()
{
    const int MAXN = 20;
    int a[MAXN];
    int i;
    for (i = 0; i < MAXN; ++i)
        a[i] = rand() % (MAXN * 2);

    //动态申请vector 并对vector建堆
    vector<int> *pvet = new vector<int>(40);
    pvet->assign(a, a + MAXN);

    //建堆
    make_heap(pvet->begin(), pvet->end());
    PrintfVectorInt(*pvet);

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

    //删除数据 要先调用pop_heap()，再在容器中删除
    pop_heap(pvet->begin(), pvet->end());
    pvet->pop_back();
    pop_heap(pvet->begin(), pvet->end());
    pvet->pop_back();
    PrintfVectorInt(*pvet);

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

    delete pvet;
    return 0;
}

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

#include<algorithm>

#include<cstdio>

using namespace std;

bool cmp(int a,int b)

{

    return a>b;

}

int main()

{

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

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

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

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

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

    printf("\n");

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

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

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

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

    printf("\n");

    //加入元素8

    number[12]=8;

    //加入后调整

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

    //结果：8 17 12 19 23 15 26 51 22 35 40 20

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

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

    printf("\n");

    //弹出元素8

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

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

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

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

    printf("\n");

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

    //结果不用说都知道是有序的了！

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

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

    return 0;

}

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

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

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

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

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

         在STL中为堆heap的创建和操作提供了4种算法：make_heap，pop_heap，push_heap和sort_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函数）。