#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;
#define SIZE 500000
void swap(int &a,int &b)
{
int temp = a;
a = b;
b = temp;
}
class Heap
{
int size;
int heap[SIZE];
public:
virtual bool cmp(int a,int b) = 0;
private:
inline int fathter(int p)
{
return p / 2;
}
inline int LeftSon(int p)
{
int son = 2 * p;
if (son > size)
return 0;
return son;
}
inline int RightSon(int p)
{
int son = 2 * p + 1;
if (son > size)
return 0;
return son;
}
int ShiftUp(int p)
{
if (p == 1)
return p;
if (cmp(heap[p],heap[fathter(p)]))
{
swap(heap[p],heap[fathter(p)]);
return fathter(p);
}
return p;
}
int ShiftDown(int p)
{
int lagest = p;
if ((LeftSon(p)) && (cmp(heap[LeftSon(p)],heap[lagest])))
lagest = LeftSon(p);
if ((RightSon(p)) && (cmp(heap[RightSon(p)],heap[lagest])))
lagest = RightSon(p);
if (lagest != p)
swap(heap[lagest],heap[p]);
return lagest;
}
public:
Heap() { size = 0; }
int insert(int n);
void del(int p);
void DelHead();
int head();
void init();
bool IsEempty();
};
int Heap::insert(int n)
{
size++;
heap[size] = n;
int where = size;
int p;
while (((p = ShiftUp(where)) != where))
{
where = p;
continue;
}
return where;
}
void Heap::del(int p)
{
heap[p] = heap[size];
size--;
int where;
while (((where = ShiftDown(p)) != p))
{
p = where;
continue;
}
}
void Heap::DelHead()
{
del(1);
}
int Heap::head()
{
if (size == 0)
return -1;
return heap[1];
}
void Heap::init()
{
size = 0;
}
bool Heap::IsEempty()
{
if (size == 0)
return 1;
else
return 0;
}
class MaxHeap : public Heap
{
bool cmp(int a,int b)
{
return a > b;
}
};
class MinHeap : public Heap
{
bool cmp(int a,int b)
{
return a < b;
}
};
int main()
{
return 0;
}