#include<iostream>
#include<cmath>
#include<stdlib.h>
#define bug cout<<"nug is here"<<endl;
#include<vector>
using namespace std;
typedef size_t ull;
 
 
//堆 
template<typename P>
class Heap{
	private:
		vector<int> heap_elem;//堆容器 
		ull heap_depth;//深度
		bool Priority; //優(yōu)先級
		ull heap_size; //容量
		
		void Up_adjust(int now);//上浮調(diào)整
		void Down_adjust(int now);//下沉調(diào)整 
		//now指代下標 
	public:
		//構造堆 
		enum{max_heap = true, min_heap = false};
		Heap(vector<P> &l, bool priority = max_heap){
			heap_size = l.size();
			heap_depth = log2(heap_size);
			Priority = priority;//設置優(yōu)先級 
			for(int i = 0;i < heap_size;i++){
				heap_elem.push_back(l[i]); 
				Up_adjust(i);//上浮調(diào)整
			} 
		}
		Heap(int a[], ull n, bool priority = max_heap){
			heap_size = n;
			heap_depth = log2(heap_size);
			Priority = priority;//設置優(yōu)先級 
			for(int i = 0;i < n;i++){
				heap_elem.push_back(a[i]);
				Up_adjust(i);//上浮調(diào)整
			}	
		}
		Heap(){
			heap_size = 0;
			heap_depth = 0;
			Priority = max_heap;
		};
	
	
		//堆的成員函數(shù)
		ull Depth(){
			return heap_depth;
		}
		ull Size(){
			return heap_size;
		}
		void Push(P x){
			heap_elem.push_back(x);
			++heap_size;
			heap_depth = log2(heap_size);
			swap(heap_elem[heap_elem.size() - 1], heap_elem[heap_size - 1]);//將加入的元素放入有效位 
			Up_adjust(heap_size - 1);
		} 
		void Pop(){
			heap_depth = log2(heap_size);
			swap(heap_elem[--heap_size], heap_elem[0]);//將第一個元素與最后一個元素交換，并且縮短有效位數(shù) 
			//其實這里可以用vector的函數(shù)pop_back（）,相應的上面的Push函數(shù)也不用換位置，但是這樣更快 
			Down_adjust(0);
		}
		P &Top(){
			return heap_elem[0];
		}
		void show_as_tree(){//以樹的形式輸出 
			int _size = max(log10(heap_elem[0]),log10(heap_elem[heap_size - 1])) + 1;
			ull max_size = (pow(2, heap_depth) * 2) * _size;
			ull _max_size = _size * pow(2, heap_depth + 1);
			int start = -1;
			for(int i = 0;i <= heap_depth;i++){
				max_size >>= 1;
				max_size++;
				if(i == heap_depth) cout<<heap_elem[++start];
				else printf("%*d",max_size,heap_elem[++start]);
				int w = pow(2, i);
				for(int j = 1;j < w && start < heap_size - 1;j++) printf("%*d",_max_size,heap_elem[++start]);
				_max_size >>= 1;
				_max_size++;
				printf("\n");
				
				
			}
		
		}
		
		void show_as_array(){//數(shù)組方式輸出 
				for(int i = 0;i < heap_size;i++) cout<<heap_elem[i]<<" ";
				cout<<endl; 
		} 
};
 
 
//上浮調(diào)整 
template<typename P>
void Heap<P>::Up_adjust(int now){
	if(Priority)
		while(now > 0 && heap_elem[now] > heap_elem[(now - 1) / 2]){//如果當前節(jié)點的權值比父親大 
			swap(heap_elem[now], heap_elem[(now - 1) / 2]);//交換 
			now =  (now - 1) / 2;
		}
	else
		while(now > 0 && heap_elem[now] < heap_elem[(now - 1) / 2]){
			swap(heap_elem[now], heap_elem[(now - 1) / 2]);
			now = (now - 1) / 2;
		}
}
 
//下沉調(diào)整 
template<typename P>
void Heap<P>::Down_adjust(int now){
	ull left = now * 2 + 1;
	ull right;
	while(left < heap_size){//能換的時候 
		left = now * 2 + 1;
		right = now * 2 + 2;
		if(Priority){
			if(heap_elem[now] < heap_elem[left]){//比左孩子小，下沉 
				swap(heap_elem[now], heap_elem[left]);
				now = left;
			}
			else if(right < heap_size){//比右孩子小，下沉 
				if(heap_elem[now] > heap_elem[right]){
					swap(heap_elem[now], heap_elem[right]);
					now = right;	
				}
				
			}
		}
		else{
			if(heap_elem[now] > heap_elem[left]){//比左孩子大，下沉 
				swap(heap_elem[now], heap_elem[left]);
				now = left;
			}
			else if(right > heap_size){//比右孩子大，下沉 
				if(heap_elem[now] < heap_elem[right]){
					swap(heap_elem[now], heap_elem[right]);
					now = right;	
				}
			}			
		}
	} 
}
 
int main(){
	int a[6] = {3,5,8,9,1,2}; 
	Heap<int> h(a, 6, true);
	//輸出堆 
	h.show_as_tree();
	
//	h.Push(12);
//	h.show_as_tree();
//	
//	h.Pop();
//	h.show_as_tree();
//	
//	cout<<h.Top()<<endl;
 
//	vector<int> a;
//	Heap<int> h(a, Heap<int>::max_heap);
//	for(int i=0;i < 10;++i)
//		h.Push(rand()%100);
//
//	h.show_as_tree();
	return 0;
}