本文共 3204 字，大约阅读时间需要 10 分钟。

我在http://blog.csdn.net/bdss58/article/details/40786355这篇博客中介绍了二叉堆的c语言实现。

这次，我将使用c++模板类技术实现这个二叉堆，使它能够存储更多的数据类型。也就是c++中的通用容器（generic collection）概念。

改写之后我们可以这样创建一个heap对象;

Heap
   
     h;
   

在C实现中，必须传递一个结构体实例的指针给函数，以便函数能够操作结构体中的数据。但是，c++可以面相对象，函数可以炒作类中的私有成员变量（将原结构体中的数据成员设计成c++的私有成员）。原来固定不变的堆最大容量max_size也可以设计到类的成员变量中。

而C中初始化函数可以设计到C++的构造函数中。

c++类中没有动态分配的变量，所以析构函数就不需要做什么了。

C实现中的那些辅助函数可以设计成c++ heap类的私有成员函数。而宏定义的函数，例如：

#define  LEFT_CHILD(index) (2 * (index) + 1)#define RIGHT_CHILD(index) (2 * (index) + 2)

下面是完整的实现代码：

/**  * this file implemente binary heap data structure  * using c++ template class  * generic collection  *  * author by jianyong-lee  * 2014/11/13  * in southwest university  *  * lisence :GPL  * */#ifndef HEAP_TEMPLATE_H#define HEAP_TEMPLATE_H#include 
   
    #include 
    
     template
     
      class Heap{public:    Heap();    ~Heap();    T get_first_value();    void add_value(T value);private:    T values[max_size];    int heap_size;    void sift_down(int index);    void sift_up(int index);    void swap_value(int index_i,int index_j);    inline int left_child(int index) {return 2*index+1;}    inline int right_child(int index) {return 2*index+2;}    inline int parent(int index) {return (index-1)/2;}};template
      
       Heap
       
        ::Heap(){        heap_size=0;}template
        
         Heap
         
          ::~Heap(){}template
          
           T Heap
           
            ::get_first_value(){ // assert(heap_size>0); if(heap_size<=0) { // throw "heap is empty!"; throw std::underflow_error("heap is empty"); } T result; result=values[0]; heap_size--; if(heap_size!=0) { values[0]=values[heap_size]; sift_down(0); } return result;}template
            
             void Heap
             
              ::add_value(T value){ // assert(heap_size
              
               max_size) { throw "heap is full"; } values[heap_size]=value; heap_size++; if((heap_size-1)!=0) { sift_up(heap_size-1); }}template
               
                void Heap
                
                 ::sift_down(int index){ int leftChild=left_child(index); int rightChild=right_child(index); if(leftChild>=heap_size) { return; } if(rightChild>=heap_size) { // only have left child if(values[leftChild]
                 
                  void Heap
                  
                   ::sift_up(int index){ if(index==0) return; int parent_index=parent(index); assert(parent_index>=0); if(values[index]
                   
                    void Heap
                    
                     ::swap_value(int index_i, int index_j){ T tmp; assert(index_i>=0 && index_i
                     
                      =0 && index_j
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

You may have noticed that the heap is careful to use only the < comparison operator to do all of its comparisons between float values. Your C++ template implementation should be the same; it should only use < for comparisons. This is done for a good reason; if you are careful in your template implementation then you can use it with any type that provides an implementation of the comparison operators.

注意到我们使用比较运算符<来完成比较操作的。所以，使用这个实例化模板类的数据类型只要支持比较运算符<就行！

例如，c++中的string类型已经实现了<运算符，所以，我们的heap类也可以存储string类型的数据。

Heap
   
     hs;hs.add_value("jianyong");
   

#include 
   
    #include "heap_template.h"using namespace std;int main(){    Heap
    
      h;    srand(11);    int i;    for(i=0;i<32;i++)    {        h.add_value(rand()%1000);    }    for(i=0;i<32;i++)    {        cout<
     
      <
      
        hs;    hs.add_value(s1);    hs.add_value(s2);    cout<
       
        <