//堆排序
//如何建立初始堆
//核心是heap_adjust,建立，调整都是在此之上

include[HTML_REMOVED]

using namespace std;

void heap_adjust(int data[],int root,int n){
data[0]=data[root];//暂存，成为虚空结点
int parent=root; //开始模拟parent和child
int child=2parent;
while(child<=n){
if(child+1<=n){
if(data[child][HTML_REMOVED]=data[child]) break;//死在这里
else{
data[parent]=data[child];
//可能会将一个很小的值传了下去，比如1
parent=child;
child=parent2;
}
}
data[parent]=data[0];
}

void heap_create(int data[],int n){
for(int i=n/2;i>=1;i–)
heap_adjust(data,i,n);
}

void heapsort(int data[],int n){
heap_create(data,n);
for(int i=n;i>1;i–)
{
int temp=data[1];
data[1]=data[i];
data[i]=temp;
heap_adjust(data,1,i-1);
}
}

void heap_insert(int data[],int n,int insert){
//这里n就是插入位置
data[0]=insert;
int parent=n/2;
int child=n;
while(parent>=1){
if(data[0]>data[parent]){
data[child]=data[parent];
child=parent;
parent=child/2;
}
}
data[child]=data[0];
//感觉就是下沉的逆过程，只有一个父节点，还不用比较大小
}//这里会超时，不知道为什么

int main()
{
int data[]={100,1,3,5,7,9,2,4,6,8,0};
// for(int i=1;i<=10;i)
// cout<<data[i]<<’ ‘;
// heapsort(data,10);
// cout<<endl;
// for(int i=1;i<=10;i)
// cout<<data[i]<<’ ‘;
//-------------这里我实现一下堆的插入和删除
heap_create(data,10);
for(int i=1;i<=10;i++)
cout<<data[i]<<’ ‘;
cout<<”初始化堆完成”<<endl;
//关于堆的删除，有点麻烦，把最后一个元素互换过去，然后成为一个插入子问题吗
//因为可能是一个大元素换过去了，一直向上找到自己的位置，上浮子问题
//这里搜了一下，堆基本就是考虑删除堆顶问题

//堆的插入就是一个上浮子问题，这里我写一下
cout<<"输入一个元素替换0，作为插入元素"<<endl;
int insert=0;
heap_insert(data,10,insert);
cout<<"调整后堆如下"<<endl;
for(int i=1;i<=10;i++)
cout<<data[i]<<' ';

}

//堆，数组看做完全二叉，满足data[i]>=data[2i]&&data[i]>=data[2i+1];

//分析
//adjust，每次调整最多跑一个树高logn
//建立堆,是一个数学问题，可以算出来为4n
//排序就是建立堆，然后n-1次调整，每次调整都不会超过logn，总体时间复杂度nlogn
//最坏情况也是nlogn，而且不需要辅助空间

//不稳定
//比较次数注意是大小孩子先比较，然后再和虚空比较，具体分析时候注意细节

//这里额外补充一下，如何插入一个元素，就是插到堆底部，然后一直向上比较
//这是我之前想过的一个错误的建立堆方式，这里因为不会把一个很小的数传下去
//因为父亲本来就很大，所以不会出现破坏性质向下传导
//网上说这里类似上浮，然后调整类似于下沉，可以这样理解