响应式全屏网站模板,公司平台网站建设,宠物网站的设计与实现,建设网站建设白度经验大根堆#xff1a;树的根节点大于左右子树的结点值#xff0c;这样就能保证每次从树根取的是最大值
灵魂在于HeadAdjust函数#xff0c;以某节点为树根通过下落调整为大根堆#xff0c;
建树思想 就是#xff0c;从最后一个非终端结点开始调整以该结点为根的子树#x…大根堆树的根节点大于左右子树的结点值这样就能保证每次从树根取的是最大值
灵魂在于HeadAdjust函数以某节点为树根通过下落调整为大根堆
建树思想 就是从最后一个非终端结点开始调整以该结点为根的子树 通过HeadAdjusth函数下落实现
排序因为树根是最大值每次取数根然后与树最后一个结点交换然后将这个点固定树的结点数减一调整根节点这棵树重新变为大根堆重复依次。
#include bits/stdc.h
using namespace std;
#define inf 0x3f3f3f
void swap(int a, int b){int tmpa;ab;btmp;
}
//子树头节点的下落
void HeadAdjust(int a[], int k, int len){a[0]a[k];//暂存子树头结点//一直下落找到最终位置 for(int ik*2; ilen; i*2){if(ilen a[i1]a[i])i;//从左右儿子中找到一个最大儿子 if(a[0]a[i])break;//找到了最终下落位置 else{//孩子比他大就下落 a[k]a[i];ki;}}a[k]a[0];//给找到的结点写回值
}
void BuildMaxHeap(int a[], int len){//a数组从1开始存//从最后一个非终端结点开始调整下落 for(int ilen/2; i1; i--){HeadAdjust(a, i, len);}
}
void HeadSort(int a[], int len){BuildMaxHeap(a, len);//建大根堆 //每次将数跟也就是最大元素与最后一个元素交换//再调整大根堆每次就能确定一个未确定的最大数 for(int ilen; i1; i--){swap(a[i], a[1]);//把最大的结点1放到树末 HeadAdjust(a, 1, i-1);//每次确定一个最大数未确定数就少一个 }
}
int main()
{int a[100];int n;cinn;for(int i1;in;i){cina[i];}HeadSort(a, n);for(int i1;in;i)couta[i]endl;return 0;
}
