堆排序---图文并茂

目录大堆与小堆堆的逻辑结构和物理结构的关联堆排序的思路分两步第一步第二步堆排序的代码升序总结版本0. 父子节点的公式转换1. 完全二叉树是不是分为“左子树大、右子树小”两种2. 如果给我一个数组我怎么把它调整成堆大堆/小堆第一步找到最后一个非叶子节点第二步从后往前对每个非叶子节点执行“向下调整”3. 堆排序到底在干什么是不是就是把数组变成堆4. 你代码里那个 AdjustDown 是怎么工作的5. 总结一下面对一个数组我怎么操作堆排序的时间复杂度**O(n log n)**大堆与小堆二者都是完全二叉树。大堆父节点的值总是大于或等于子节点大堆父节点的值总是小于或等于子节点int child parent * 2 1; 父节点与子节点下标关系堆的逻辑结构和物理结构的关联物理结构是一个数组而逻辑结构是一个完全二叉树。堆排序的思路分两步例子如下现有数组a[]{1,9,3,4,8,3},要将其升序排列。第一步第一步要求升序则将其原堆建为大堆若要求降序则将其原堆建为小堆(原因在最后会讲)如何将原堆建为大堆用大白话讲就是先找到最后一层最右边的那一个叶子节点a再找a的父节点b从b开始进行向下调整操作然后遍历数组,重复向下调整操作下标减小直到0结束)。向下调整操作的代码voidAdjustDown(int*a,intn,intparent)// n是 要调整的堆 的 最后一个数 的下标1{//parent就是图中的父节点的下标intchildparent*21;while(childn){// 选出左右孩子中小/大的那个假设法if(child1na[child1]a[child])//child 1 n确保有右孩子才进行比较防越界{child;//此时孩子为右孩子}if(a[child]a[parent]){Swap(a[parent],a[child]);//父子交换parentchild;childparent*21;//父子向下更替}else{break;}}}纵观全过程每一个进行向下调整操作的数其左子树和右子树都是大堆其实这就是向下调整操作能进行的前提条件。第二步第二步堆顶与最后一个数进行交换将最后一个数不看做堆里的数堆里的数减少一个在堆顶处进行向下调整操作。重复操作直到堆里没有数。此刻整个数组已有序堆排序完成。第一步的若要求升序则将其原堆建为大堆若要求降序则将其原堆建为小堆在这里就明白了因为堆顶与最后一位进行了交换那么最大值其实在最后一位。堆排序的代码升序#includestdio.hvoidSwap(int*p1,int*p2)//交换函数{inttmp*p1;*p1*p2;*p2tmp;}voidAdjustDown(int*a,intn,intparent)// n是 要调整的堆 的 最后一个数 的下标1{//parent就是图中的父节点的下标intchildparent*21;while(childn){// 选出左右孩子中小/大的那个假设法if(child1na[child1]a[child])//child 1 n确保有右孩子才进行比较防越界{child;//此时孩子为右孩子}if(a[child]a[parent]){Swap(a[parent],a[child]);//父子交换parentchild;childparent*21;//父子向下更替}else{break;}}}voidHeapSort(int*a,intn){// 升序 -- 建大堆// 降序 -- 建小堆// 建堆--向下调整建堆 --O(N)for(inti(n-1-1)/2;i0;--i)//(n - 1 - 1) / 2:文中所指的b点的下标 遍历的过程{AdjustDown(a,n,i);}intendn-1;while(end0){Swap(a[0],a[end]);// 再调整选出次大的数AdjustDown(a,end,0);// end是 “要调整的堆” 的 最后一个数 的下标1--end;// “要调整的堆” 的 最后一个数一直在变因为堆中的数在变少}}intmain(){inta[]{1,9,3,4,8,3};intnsizeof(a)/sizeof(int);HeapSort(a,n);for(inti0;in;i){printf(%d ,a[i]);}return0;}执行结果为你提的这些问题很关键我来帮你把“堆、建堆、堆排序”彻底理清楚。先直接回答你最核心的几个疑问。总结版本0. 父子节点的公式转换已知子节点可以推出父节点✅已知父节点可以推出子节点✅已知子节点下标child推父节点下标parent公式parent (child - 1) / 2整数除法向下取整已知父节点下标parent推子节点下标公式左孩子left parent * 2 1右孩子right parent * 2 21. 完全二叉树是不是分为“左子树大、右子树小”两种不是。你混淆了二叉搜索树BST和堆。二叉搜索树左子树所有节点 根 右子树所有节点所以中序遍历是升序。堆大堆/小堆只要求父节点 子节点大堆或 子节点小堆左右孩子之间没有任何大小关系约束。所以完全二叉树只是形状最后一层靠左连续而堆是在这个形状上加了值的大小规则但不分左右。2. 如果给我一个数组我怎么把它调整成堆大堆/小堆步骤非常简单就两步第一步找到最后一个非叶子节点数组长度n最后一个元素下标是n-1。它的父节点下标是(n-1-1)/2 (n-2)/2这就是最后一个非叶子节点。第二步从后往前对每个非叶子节点执行“向下调整”从i (n-2)/2开始i--一直做到i0。对每个i调用AdjustDown(a, n, i)。为什么要从后往前因为向下调整的前提是当前节点的左右子树必须已经是堆。从最后一个非叶子节点开始它的左右孩子都是叶子节点单个节点可视为堆满足前提然后一步步往上就能把整棵树建成堆。用你给的代码就是for(inti(n-1-1)/2;i0;--i){AdjustDown(a,n,i);}这一步就叫建堆时间复杂度 O(N)。3. 堆排序到底在干什么是不是就是把数组变成堆堆排序 ≠ 建堆。堆排序分两步建堆把数组变成大堆或小堆。排序利用堆的性质反复取堆顶放到数组末尾最终使数组有序。举个例子升序排列先建大堆→ 堆顶是最大值。把堆顶a[0]和最后一个元素a[n-1]交换 → 最大值到了末尾。然后把末尾元素“移出堆”end--再对新的堆顶执行向下调整重新形成大堆。重复上述过程每次把当前最大值放到末尾最终整个数组升序。所以堆排序的最终结果是一个有序数组不是堆。建堆只是中间状态。4. 你代码里那个 AdjustDown 是怎么工作的AdjustDown的作用是假设左右子树都已经是大堆或小堆把父节点“沉”下去使整棵树恢复堆性质。具体逻辑找到父节点的左孩子child parent*21。如果有右孩子且右孩子更大大堆就选右孩子。如果孩子比父节点大交换然后继续向下调整。否则停止。5. 总结一下面对一个数组我怎么操作给你一个数组a[]要升序排序// 1. 建大堆for(inti(n-2)/2;i0;--i)AdjustDown(a,n,i);// 2. 排序intendn-1;while(end0){Swap(a[0],a[end]);// 堆顶放末尾AdjustDown(a,end,0);// 对剩余部分重新调整成大堆--end;}最终a[]就是升序的。堆排序的时间复杂度O(n log n)分两步算清清楚楚堆排序 建堆排序两步分开算第一步建堆建大堆/小堆for(inti(n-1-1)/2;i0;--i){AdjustDown(a,n,i);}每个节点向下调整最多走树的高度步O(log n)但不是所有节点都走 log n 步——叶子节点占一半根本不动越往上节点越少但走的路程越长精确计算下来总时间复杂度是O(n)不是 O(n log n)记住结论建堆是 O(n)第二步排序反复取堆顶intendn-1;while(end0){Swap(a[0],a[end]);// 交换堆顶和末尾AdjustDown(a,end,0);// 堆顶向下调整--end;}循环执行n-1次每次执行AdjustDown从堆顶走到叶子走树的高度步 O(log n)总时间 n × O(log n) O(n log n)总时间复杂度步骤时间复杂度建堆O(n)排序O(n log n)堆排序总计O(n log n)总结一句话堆排序的时间复杂度 O(n log n)空间复杂度 O(1)是不稳定的排序算法。注意稳定性指的是相同值的元素在排序后相对顺序是否改变堆排序在交换堆顶和末尾时可能改变相同值的顺序所以不稳定。