[ min-max heap ] 最小-最大堆

最小-最大堆(Min-Max Heaps)是一個完整二元樹。此二元樹是交替的階層方式呈現，分別為最小階層 ( min level ) 和最大階層 ( max level ) ，這裡實作樹根為最小鍵值。

最小-最大堆是一種堆積支援以下幾種操作:

1. 求最大值 - max()
2. 求最小值 - min()
3. 刪除最大值 - pop_max()
4. 刪除最小值 - pop_min()
5. 元素入堆 - push()

詳細演算法可以參考原始論文
Min-Max Heaps and Generalized Priority Queues

如果不懂敘述就看code吧
以下提供模板:

	#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

view raw minmax_heap.cpp hosted with ❤ by GitHub