（一）用仿函数实现大堆小堆

堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。

堆结构的二叉树存储是

最大堆：每个父节点的都大于孩子节点。

最小堆：每个父节点的都小于孩子节点。

仿函数(functor)，就是使一个类的使用看上去象一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。
在实现大，小堆的过程中，有些功能的的代码，会在不同的成员函数中用到，想复用这些代码，有两种途径。

1）公共的函数，这是一个解决方法，不过函数用到的一些变量，就可能成为公共的全局变量，再说为了复用这么一片代码，就要单立出一个函数，也不是很好维护。

2）仿函数，写一个简单类，除了那些维护一个类的成员函数外，就只是实现一个operator()，在类实例化时，就将要用的，非参数的元素传入类中。

在C++里，我们通过在一个类中重载括号运算符的方法使用一个函数对象而不是一个普通函数

Heap.h#include<iostream>#include<algorithm>usingnamespacestd;template<typenameT>classdisplay{public:voidoperator()(constT&x){cout<<x<<"";}};intmain(){intia[]={1,2,3,4,5};for_each(ia,ia+5,display<int>());return0;}

用仿函数实现大堆，小堆的基本结构

#include<iostream>#include<vector>usingnamespacestd;template<classT>structLess//小于{booloperator()(constT&l,constT&r){returnl<r;}};template<classT>structGreater{booloperator()(constT&l,constT&r){returnl>r;}};template<classT,classComper=Greater<T>>//默认建大堆classHeap{private:vector<T>_a;public:Heap(constT*a,size_tsize){assert(a);//将数组中的数据压入栈中for(i=0;i<size;i++){_a.push_back(a[i]);}//建大堆for(inti=(_a.size()-2)/2;i>=0;i--){//向下调整_AdjustDown(i);}}//向堆中插入数据voidpush(constT&x){_a.push_back(x);_Adjustup(_a.size()-1)}/********************在弹出的时候使用的方法是先将完全二叉树的根节点与最后一个叶子节点交换，弹出当前的叶子节点,然后在向下调整************************/voidpop(){swap(_a[0],_a[_a.size()-1]);_a.pop_back();_AdjustDown(0);}size_tSize()//求堆的大小{return_a.size();}boolEmpty()//堆是否为空{return_a.empty();}protected:void_AdjustDown(size_tparent){size_tchild=2*parent+1;while(child<_a.size()){Compercom;//找出两个孩子中最大的一个if(com(_a[child+1],_a[child])&&child+1<_a.size())//因为是完全二叉树所以右孩子可能不存在{child=child+1;}//如果孩子大于父亲则交换继续往下调整if(com(_a[child],_a[parent])){swap(_a[child],_a[parent]);parent=child;child=2*parent+1;}//否则满足大根堆，退出循环else{break;}}}//向上调整void_Adjustup(size_tchild){size_tparent=(child-1)/2;while(child>0)//不能写成while(parent>0),因为child为size_t类型，会构成死循环{Compercom;//如果插入的子节点大于根节点，则交换if(com(_a[child],_a[parent])){swap(_a[child],_a[parent]);child=parent;parent=(child-1)/2;}//否则满足大堆，退出循环else{break;}}}};

(二)堆排序

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>#include<assert.h>usingnamespacestd;//建初堆，大堆voidAdjustDown(inta[],intn,intparent){intchild=parent*2+1;while(child<n){if(child+1<n&&a[child]<a[child+1]){++child;}if(a[child]>a[parent]){swap(a[child],a[parent]);parent=child;child=parent*2+1;}else{break;}}}voidHeapSort(inta[],intn){assert(a);//建大堆for(inti=(n-2)/2;i>=0;i--){AdjustDown(a,n,i);}//选出一个数据交换到末尾,利用帅选法将前N-i个元素重新帅选建成一个堆for(inti=n-1;i>0;i--){swap(a[0],a[i]);AdjustDown(a,i,0);}}voidtest(){inta[8]={98,77,35,62,55,14,35,48};intsize=sizeof(a)/sizeof(a[0]);HeapSort(a,size);for(inti=0;i<size;i++){cout<<a[i]<<"";}cout<<endl;}intmain(){test();system("pause");return0;}