对顶堆

template<typename T>
class mid_heap//对顶堆
{
	private:
		priority_queue<T>big;
		priority_queue<T,vector<T>,greater<T> >small;
		void ph()
		{
			if(big.size()<small.size())
				big.push(small.top()),small.pop();
			if(big.size()-small.size()>1)
				small.push(big.top()),big.pop();
		}
	public:
		T top()
		{
			return big.top();
		}
		void push(T x)
		{
			if(small.size() && x>small.top())small.push(x);
			else big.push(x);
			ph();
		}
		void pop()
		{
			big.pop();
			ph();
		}
		unsigned long long size()
		{
			return big.size()+small.size();
		}
		bool empty()
		{
			return size()==0;
		}
};

可删堆

template<typename T,typename Tv=vector<T>,typename Tl_g=less<T> >
class del_heap//可删堆 
{
	private:
		priority_queue<T,Tv,Tl_g>q;
		priority_queue<T,Tv,Tl_g>d;
		void ph()
		{
			while(q.size() && d.size() && q.top()==d.top())
				q.pop(),d.pop();
		}
	public:
		T top()
		{
			ph();
			return q.top();
		}
		void push(T x)
		{
			q.push(x);
		}
		void pop(T x)
		{
			d.push(x);
		}
		void pop()
		{
			pop(q.top());
		}
		unsigned long long size()
		{
			return q.size()-d.size();
		}
		bool empty()
		{
			return size()==0;
		}
};