Kopiec

template <typename T>
struct Heap
{
       int n;
       vector< T > tab;
 
       Heap () { n=0; }
       Heap (int size)  { tab.resize(size+1); n=0; }
       int  max()   { return tab[1]; }
       bool empty() { return n==0; }
 
       bool insert(T x)
       {
            n++;
            if (n>=tab.size()) tab.resize(2*n);
            tab[n]=x;
            sift_up(n);
       }         
 
       bool delMax()
       {
            if (n<1) return false;
 
            tab[1]=tab[n]; n--;
            sift_down(1);
            return true;
       }
 
	void sift_up(int x)
	{
		int p; T mem = tab[x];
		while (x>1)
		{
			p=x/2;
			if (mem<tab[p]) break;
			tab[x]=tab[p];
			x=p;
		}
		tab[x]=mem;
	}
 
	void sift_down (int x)
	{
		int s=2*x; T mem=tab[x];
		while(s<=n)
		{
			if (s+1<=n && tab[s]<tab[s+1]) s++;
			if (mem<tab[s])
			{
				tab[x]=tab[s];
				x=s;
				s=2*x;
			}
			else break;
		}
		tab[x]=mem;
	}
 
	void write ()
	{
		for (int i=1;i<=n;i++) printf ("%d) %d\n", i, tab[i]);
		printf ("\n");
	}       
 
	void build()
	{
		int s = n;
		for (s=n/2; s>=1; s--) sift_down(s);
	}
};

int main(void)
{
	Heap<int> H;
 
	cin >> H.n;                                  // wczytujemy rozmiar kopca
	H.tab.resize(H.n+1);
	for (int i=1; i<=H.n; i++) cin >> H.tab[i];  // po kolei wczytujemy liczby do zbioru
 
	H.build(); // tworzymy porządek kopcowy w czasie O(n), czyli liniowym
//	sort(H.tab+1, H.tab+H.n+1); // można byłoby zrobić tak, ale to działa w czasie O(n log(n))
 
	H.insert(10);
	cout << H.max() << endl;
	H.delMax();
	cout << H.max() << endl;
	H.delMax();
	cout << H.max() << endl;
	H.insert(100);
	cout << H.max() << endl;
}

#include<queue>
using namespace stdl
int main()
{
	priority_queue<int> Q;
	Q.push(1); // insert(1)
	Q.push(4); // insert(4)
	Q.push(2); // insert(2)
	Q.push(8); // insert(8)
	Q.push(5); // insert(5)
	Q.push(7); // insert(7)
 
	Q.pop();   // delMax()
	Q.top();   // max()
	Q.empty(); // empty()
}