1 //头文件定义--heap.h 2 #ifndef _MAXHEAP_H_ 3 #define _MAXHEAP_H_ 4 template
     
       5 class MaxHeap{ 6 public: 7     MaxHeap(int size=10); 8     virtual ~MaxHeap(); 9 10     bool IsEmpty();11     void Pop();12     void Push(const T&);13     const T& Top()const;14 private:15     int current_size;//堆的当前节点个数16     int max_size;//设置堆的最大节点个数17     T *heap_array;18 19     void TrickleUp(int index);//插入新节点（末尾），接着向上渗透20     void TrickleDown(int index);//删除根节点（用最后一个节点补到根节点），接着向下渗透21 };22 #endif
     

1 #include
     
       2 using namespace std; 3 #include"Heap.h" 4 template
      
        5 MaxHeap
       
        ::MaxHeap(int size = 10) 6 { 7     if (size < 1) 8         throw "max size must be >=1"; 9     max_size = size;10     current_size = 0;11     heap_array = new T[max_size];//int *a = new int[100];开辟一个大小为100的整型数组空间12 }13 14 template
        
         15 bool MaxHeap
         
          ::IsEmpty()16 {17     return current_size == 0;18 }19 20 template
          
           21 MaxHeap
           
            ::~MaxHeap()22 {23 delete[] heap_array;24 }25 26 template
            
             27 void MaxHeap
             
              ::Push(const T& e)28 {29 if (current_size == max_size) throw "max_array is full";30 heap_array[current_size] = e;31 TrickleUp(current_size++);32 }33 34 template
              
               35 void MaxHeap
               
                ::TrickleUp(int index)//向上渗透，将新插入的元素向上调整到合适的位置36 {37 T bottom = heap_array[index];38 int parent = (index - 1) / 2;39 while (index > 0 && heap_array[parent] < bottom)//注意这个地方自己第一次写成了heap_array[parent]
                
                 49 void MaxHeap
                 
                  ::Pop()50 {51 heap_array[0] = heap_array[--current_size];52 TrickleDown(0);53 }54 55 template
                  
                   56 const T& MaxHeap
                   
                    ::Top()const57 {58 return heap_array[0];59 }60 61 template
                    
                     62 void MaxHeap
                     
                      ::TrickleDown(int index)//向下渗透，将当前位置的元素向下调整到合适位置，保持大根堆的性质63 {64 T top = heap_array[index];65 int larger_child;66 while (index < current_size / 2)//这是完全二叉树的性质（最后一个非叶子节点的位置索引），好好体会67 {68 int lchild = 2 * index + 1;69 int rchild = 2 * (index + 1);70 if (rchild < current_size && heap_array[lchild] < heap_array[rchild])71 larger_child = rchild;72 else larger_child = lchild;73 if (top >= heap_array[index])//!!74 break;75 heap_array[index] = heap_array[larger_child];76 index = larger_child;77 }78 heap_array[index] = top;//这一句我第一次写时遗漏了79 }80 81 int main()82 {83 MaxHeap
                      
                        heap(20);84 cout << heap.IsEmpty() << endl;;85 heap.Push(7);86 heap.Push(24);87 heap.Push(9);88 cout << heap.Top() << endl;89 heap.Push(25);90 heap.Push(28);91 cout << heap.Top() << endl;92 heap.Pop();93 heap.Pop();94 cout << heap.Top() << endl;95 96 return 0;97 }
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 参考猎豹数据结构和算法讲解！