Min-Max Heap

minmax_heap.cpp

#ifndef SUNMOON_MIN_MAX_HEAP
#define SUNMOON_MIN_MAX_HEAP
#include<vector>
#include<algorithm>
template<typename T,typename _Seq=std::vector<T>,typename _Compare=std::less<T> >
class minmax_heap{
	_Seq s;
	_Compare cmp;
	bool is_min_level(size_t id){
		return !(std::__lg(++id)%2);
	}
	void TrickleDown(size_t id){
		if(is_min_level(id)) TrickleDownMin(id);
		else TrickleDownMax(id);
	}
	size_t get_min_descendant(size_t id){
		size_t res=(++id)*2-1;
		for(size_t i=2;i<=4;i*=2){
			for(size_t j=0;j<i;++j){
				int descendant=id*i+j-1;
				if(descendant>=s.size()) return res;
				if(cmp(s[descendant],s[res])){
					res=descendant;
				}
			}
		}
		return res;
	}
	void TrickleDownMin(size_t id){
		while((id+1)*2<=s.size()){
			size_t m=get_min_descendant(id);
			if(cmp(s[m],s[id])){
				std::swap(s[m],s[id]);
				if(m<=(id+1)*2) return;
				if(cmp(s[(m+1)/2-1],s[m])){
					std::swap(s[(m+1)/2-1],s[m]);
				}
				id=m;
			}else return;
		}
	}
	size_t get_max_descendant(size_t id){
		size_t res=(++id)*2-1;
		for(size_t i=2;i<=4;i*=2){
			for(size_t j=0;j<i;++j){
				int descendant=id*i+j-1;
				if(descendant>=s.size()) return res;
				if(cmp(s[res],s[descendant])){
					res=descendant;
				}
			}
		}
		return res;
	}
	void TrickleDownMax(size_t id){
		while((id+1)*2<=s.size()){
			size_t m=get_max_descendant(id);
			if(cmp(s[id],s[m])){
				std::swap(s[m],s[id]);
				if(m<=(id+1)*2) return;
				if(cmp(s[m],s[(m+1)/2-1])){
					std::swap(s[(m+1)/2-1],s[m]);
				}
				id=m;
			}else return;
		}
	}
	void BubbleUp(size_t id){
		if(!id) return;
		int parent=(id+1)/2-1;
		if(is_min_level(id)){
			if(cmp(s[parent],s[id])){
				std::swap(s[parent],s[id]);
				BubbleUpMax(parent);
			}else BubbleUpMin(id);
		}else{
			if(cmp(s[id],s[parent])){
				std::swap(s[parent],s[id]);
				BubbleUpMin(parent);
			}else BubbleUpMax(id);
		}
	}
	void BubbleUpMin(size_t id){
		while(id>2){
			int grandparent=(id+1)/4-1;
			if(cmp(s[id],s[grandparent])){
				std::swap(s[id],s[grandparent]);
				id=grandparent;
			}else break;
		}
	}
	void BubbleUpMax(size_t id){
		while(id>2){
			int grandparent=(id+1)/4-1;
			if(cmp(s[grandparent],s[id])){
				std::swap(s[id],s[grandparent]);
				id=grandparent;
			}else break;
		}
	}
	size_t find_max_id()const{
		size_t res=0,n=std::min(s.size(),size_t(3));
		while(--n) if(cmp(s[res],s[n])) res=n;
		return res;
	}
	void erase_id(size_t id){
		s[id]=s.back();
		s.pop_back();
		TrickleDown(id);
	}
public:
	bool empty()const{
		return s.empty();
	}
	int size()const{
		return s.size();
	}
	void push(const T&data){
		s.push_back(data);
		BubbleUp(s.size()-1);
	}
	const T&max()const{
		return s[find_max_id()];
	}
	const T&min()const{
		return s[0];
	}
	void pop_max(){
		erase_id(find_max_id());
	}
	void pop_min(){
		erase_id(0);
	}
};
#endif