Heap sort

heap_sort.md

##Heap sort

• Using template
• Using functional
• Using vector

        #include <iostream>
        #include <vector>
        #include <algorithm>
        #include <functional>
        
        using namespace std;
        template<class T>
        class heap{
        public:
        	heap(const vector<T>& a){
        		_data = a;
        	}
        	template<typename Comp>
        	void sort_heap(Comp p);
        
        	void print();
        private:
        	template<typename Comp>
        	void build_heap(Comp p);
        
        	template<typename Comp>
        	void heap_fixup(int i,Comp p);
        
        	vector<T> _data;
        };
        template<class T>
        template<typename Comp>
        void heap<T>::sort_heap(Comp p){
        	build_heap(p);
        	vector<T> result;
        
        	for(int i = _data.size() - 1; i >= 0; --i){
        		result.push_back(_data[0]);
        		swap(_data[i],_data[0]);
        		_data.pop_back();
        		heap_fixup(0,p);
        	}
        
        	_data = result;
        }
        
        template<class T>
        template<typename Comp>
        void heap<T>::build_heap(Comp p){
        	for(int i = _data.size() / 2 - 1; i >= 0; --i){
        		heap_fixup(i,p);
        	}
        }
        
        template<class T>
        template<typename Comp>
        void heap<T>::heap_fixup(int i,Comp p){
        	int min;
        	int index = i;
        	while(index*2 + 1 < _data.size()){
                //left child
        		min = index*2 + 1;
                //check right
        		if(min + 1 < _data.size()){
        			if(p(_data[min + 1],_data[min])){
        				min = min + 1;
        			}
        		}
                //parent match
        		if(p(_data[index],_data[min])){
        			break;
        		}else{
        			swap(_data[index],_data[min]);
        			index = min;
        		}
        	}
        }
        template<class T>
        void heap<T>::print(){
        	for(int i = 0 ; i < _data.size(); ++i){
        		cout<<_data[i]<<" ";
        	}
        	cout<<endl;
        }
        int main()
        {
        	int a[10] = {1,3,5,2,7,9,10,14,0,20};
        	vector<int> test(a,a+10);
        
        	heap<int> h(test);
        
        	h.sort_heap(less<int>());
        	h.print();
        
        	random_shuffle(test.begin(),test.end());
        	h.sort_heap(greater<int>());
        	h.print();
        
        	system("pause");
        	return 0;
        }