一流的天津网站建设武义住房和城乡建设局网站

一流的天津网站建设,武义住房和城乡建设局网站,怎么学做网站PHP,网站模板如何修改域名堆排序 学习目标 1.堆结构 2.堆排序思想 3.代码实现 4.复杂度分析 1.堆结构 定义 符合以下两个条件之一的完全二叉树 根节点的值 子节点的值#xff0c;称为最大堆#xff0c;或大顶堆根节点的值 子节点的值#xff0c;称为最小堆#xff0c;或小顶堆 …堆排序学习目标1.堆结构2.堆排序思想3.代码实现4.复杂度分析1.堆结构定义符合以下两个条件之一的完全二叉树根节点的值 子节点的值称为最大堆或大顶堆根节点的值 子节点的值称为最小堆或小顶堆2.堆排序思想(1)用数列构建出一个大顶堆取出堆顶的数字将数组看作一颗完全二叉树补充完全二叉树的性质将根节点的下标视为0则第 i 个数的左子节点下表为 2i 1 右子节点下标为 2i 2对于有n个元素的完全二叉树(n2)它的最后一个非叶子节点的下标n/2 - 1初始化堆初赛最后一个非叶子节点与其子节点 先进行比较初赛冠军站到三人组的根节点位置并进行复赛9 与 6 交换复赛循环与其父节点再进行比较 直到根节点决赛与根节点比较9 与 4 交换9 与 4 发生交换 并不意味 4 就该处在这个位置 它只是生来就处在上层下沉与 9 之前的“对手”比较只要当三人组中父节点与子节点发生了交换都需要下沉比较直到找到了自己的真正位置(2)取出堆顶数字调整剩余数字构建出新的大顶堆再次取出堆顶的数字取出堆顶数字将堆顶数字与最后一个叶节点交换也就是将数组末尾的数字交换到堆顶该数字一定是个叶子节点使得完全二叉树的结果不会被破坏记录从堆顶交换下来的数字总数节省空间调整剩余数字因为其他三人组结构没有被破坏此时只需从根节点 4 开始向下进行三人组比较(3)循环往复完成整个排序取8下沉取6下沉取54无法下沉 排序完成3.代码实现/** * 堆排序 * param arr */publicstaticvoidheapSort(int[]arr){//堆排序第一步初始化堆//这里选择构建大顶堆从小到大排序buildMaxHeap(arr);//取数字,调整 循环//取出堆顶数字与数组末尾元素交换//数组长度-1for(intiarr.length-1;i0;i--){swap(arr,0,i);//i也可以代表数组中可用的数字maxHeapify(arr,0,i);}}/** * 初始化堆(大顶堆) * param arr */privatestaticvoidbuildMaxHeap(int[]arr){//构建堆第一步从最后一个非叶子节点开始进行三人组比赛//也可以从arr.length - 1 开始,但它没有左右子节点也会运算到arr.length / 2 - 1for(intiarr.length/2-1;i0;i--){//大顶堆化maxHeapify(arr,i,arr.length);}}/** * 大顶堆化 * param arr * param i * param heapSize */privatestaticvoidmaxHeapify(int[]arr,inti,intheapSize){//找到左右子节点intl2*i1;intr2*i2;intlargesti;//不能越界if(lheapSizearr[l]arr[largest]){largestl;}if(rheapSizearr[r]arr[largest]){largestr;}if(largest!i){//需要发生交换swap(arr,i,largest);//发生了交换 则交换下来的元素需要继续下沉maxHeapify(arr,largest,heapSize);}}privatestaticvoidswap(int[]arr,inta,intb){inttemparr[a];arr[a]arr[b];arr[b]temp;}4.复杂度分析时间复杂度O(nlogn)初始化建堆O(n)重建堆O(nlogn)空间复杂度O(1)215. 数组中的第K个最大元素 - 力扣LeetCode