MyHeap.h

#ifndef MY_HEAP_H#define MY_HEAP_H#include
    
     #include
     
      #define max_value 99999999//仿函数template
      
       struct MyLess{	bool operator()(const T& x, const T& y) const { return x < y; }};template
       
        struct MyGreater{	bool operator()(const T& x, const T& y) const { return x > y; }};template
        
         >class MyHeap{private:	std::vector
         
           vec; //堆的底层容器 int num_of_element; //堆中元素个数 const int start_index = 1; //堆在底层容器中从位置1开始 Compare comp;public: //用了一个小技巧，将vector的#0元素保留，可知某节点位于vector的i处时，其左子节点位于2*i处，右子节点位于2*i+1处，父节点位于i/2处 MyHeap() :num_of_element(0){ vec.push_back(max_value); } template
          
            void initial_heap(RandomAccessIterator begin, RandomAccessIterator end); void push_heap(T element); void pop_heap(); void sort_heap(); void make_heap(); void percolate_up(int hole_index, T value); //上溯程序 void adjust_heap(int hole_index, T value); //调整程序，包括下溯操作和上溯操作 void print_heap(); std::vector
           
            & get_vector(){ return vec; }};//initial_heap(RandomAccessIterator begin, RandomAccessIterator end)template
            
             template
             
              void MyHeap
              
               ::initial_heap(RandomAccessIterator begin, RandomAccessIterator end){ for (RandomAccessIterator it = begin; it != end; ++it){ vec.push_back(*it); ++num_of_element; }}//push_heap(T element)template
               
                void MyHeap
                
                 ::push_heap(T element){ vec.push_back(element); ++num_of_element; percolate_up(num_of_element, element);}//percolate_up(int hole_index, T value)template
                 
                  void MyHeap
                  
                   ::percolate_up(int hole_index, T value){ int parent = hole_index / 2; //找出洞节点的父节点 while (hole_index > start_index&&comp(vec[parent], value)){//没到顶点且父值小于插入值 vec[hole_index] = vec[parent];//洞值为父值 hole_index = parent; //调整洞号 parent = hole_index / 2; //新洞的父节点 } vec[hole_index] = value; //洞值为插入值}//pop_heap()template
                   
                    void MyHeap
                    
                     ::pop_heap(){ T adjust_value = vec[num_of_element];//堆的最后一个节点需要调整 vec[num_of_element] = vec[start_index];//vec中最后一个元素为最大值 --num_of_element; //堆中元素减1 adjust_heap(start_index, adjust_value);}//adjust_heap(int hole_index, T value)template
                     
                      void MyHeap
                      
                       ::adjust_heap(int hole_index, T value){ int right_child = 2 * hole_index + 1; //洞节点的右子节点 while (right_child <= num_of_element){ if (comp(vec[right_child], vec[right_child - 1])) //比较左右两个子节点的值 --right_child; vec[hole_index] = vec[right_child];//洞值为左右两个子节点中较大的值 hole_index = right_child; //调整洞号 right_child = 2 * hole_index + 1; //新洞节点的右子节点 } if (right_child == num_of_element + 1){ //没有右子节点，只有左子节点 vec[hole_index] = vec[right_child - 1]; //左子值为洞值 hole_index = right_child - 1;//洞节点为左子节点 } vec[hole_index] = value; //洞值为插入值 //percolate_up(hole_index, value); //此时可能尚未满足次序特性，执行上溯操作,可能有问题 //注意，跟STL源码剖析说执行一次percolate up操作有区别，执行一次可能会出错 int yejiedian = num_of_element; while (yejiedian >= hole_index){ percolate_up(yejiedian, vec[yejiedian]); //此时可能尚未满足次序特性，执行上溯操作 --yejiedian; }}//sort_heap()template
                       
                        void MyHeap
                        
                         ::sort_heap(){ while (num_of_element > 0) pop_heap();}//make_heap()template
                         
                          void MyHeap
                          
                           ::make_heap(){ //cout << "make heap过程：" << endl; if (num_of_element < 2) //长度为0或1,不必重新排列 return; int parent = num_of_element / 2; //第一个需要重排的子树头部 while (true){ adjust_heap(parent, vec[parent]); //print_heap(); if (parent == 1) //走完根节点就结束 return; --parent; }}//print_heap()template
                           
                            void MyHeap
                            
                             ::print_heap(){ for (int i = 1; i <= num_of_element; ++i) std::cout << vec[i] << " "; std::cout << std::endl;}#endif
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

MyPriorityQueue.h

#ifndef MY_PRORITY_QUEUE_h#define MY_PRORITY_QUEUE_h#include "MyHeap.h"template
    
     >class MyPriorityQueue{private:	MyHeap
     
       heap; //底层用堆实现	const int top_index = 1;public:	MyPriorityQueue() :heap(){}	template
      
       	MyPriorityQueue(InputIterator first, InputIterator last){		heap.initial_heap(first, last);		heap.make_heap();	}	bool empty(){ return heap.get_vector().size() == 1; } //注意heap的底层的vector第一个元素保留	int size(){ return heap.get_vector().size() - 1; }	T top(){ return heap.get_vector()[top_index]; }	void push(const T& t){		heap.push_heap(t);	}	void pop(){		heap.pop_heap();		heap.get_vector().erase(--heap.get_vector().end());	}};#endif
      
     
    

main.cpp

#include "MyPriorityQueue.h"using namespace std;int main(){	int ia[] = { 24, 26, 31, 13, 19, 21, 65, 68, 16 };	MyPriorityQueue
    
      que1(begin(ia), end(ia));	cout << "top:" << que1.top() << endl; //top:68	cout << "size:" << que1.size() << endl;//size:9	que1.pop();	cout << "top:" << que1.top() << endl;//top:65	cout << "size:" << que1.size() << endl;//size:8	que1.push(100);	cout << "top:" << que1.top() << endl; //top:100	cout << "size:" << que1.size() << endl;//size:9	cout << endl;	MyPriorityQueue
     
      
       > que2(begin(ia), end(ia));	cout << "top:" << que2.top() << endl; //top:13	cout << "size:" << que2.size() << endl;//size:9	que2.pop();	cout << "top:" << que2.top() << endl;//top:16	cout << "size:" << que2.size() << endl;//size:8	que2.push(1);	cout << "top:" << que2.top() << endl;//top:1	cout << "size:" << que2.size() << endl;//size:9	cout << endl;	MyPriorityQueue
       
         que3;	cout << (que3.empty() ? "empty" : "not empty") << endl;//empty	que3.push(3);	que3.push(2);	que3.push(4);	que3.push(5);	que3.push(1);	cout << "top:" << que3.top() << endl; //top:5	cout << "size:" << que3.size() << endl;//size:5	que3.pop();	cout << "top:" << que3.top() << endl;//top:4	cout << "size:" << que3.size() << endl;//size:4	system("pause");	return 0;}