//C++动态数组简单的模拟二元堆
#include<iostream>
using namespace std;
class BinaryHeap
{
private:
int cap;  //该阵列的大容量
int size; //当前元素个数
int* datas; //数组首地址
public:
explicit BinaryHeap(int cap_) :cap(cap_)， size(0)
{
datas = new int[cap];
}
~BinaryHeap(){ delete datas; }
void Insert(int);
int DeleteMin();
};
//用数组表示的树，当下标从0?始时，i为当前节点，i*2+1为i的左子树节点，i*2+2为i的右子树节点，i/2为i的父节点
void BinaryHeap::Insert(int data)
{
int i;
for (i = size; i / 2 >= 0 && datas[i / 2] > data; i /= 2) //上滤
{
datas[i] = datas[i / 2];
}
datas[i] = data;
size++;
}
int BinaryHeap::DeleteMin()
{
int i = 0， child = 0;
int lastdata = datas[--size];
int mindata = datas[0];
for (i = 0; i * 2 + 1 <= size-1; i = child)   //下滤
{
child = i * 2 + 1;
if (child < size-1 && datas[child + 1] < datas[child])
{
child++;
}
if (lastdata > datas[child])
{
datas[i] = datas[child];
}
else
{
break;
}
}
datas[i] = lastdata;
return mindata;
}
int main()
{
BinaryHeap t(400);
for (int i = 0; i < 100; i++)
t.Insert(i);
for (int i = 200; i > 100; i--)
t.Insert(i);
for (int i = 0; i < 200; i++)
cout << t.DeleteMin() << endl;
cin.get();
return 0;
}