int start，大根堆就是上面元素是最大的而已怎么构建还都是一样啊就是把大元素往上覆盖判断条件变了而已 现在你首元素最小了说明逻辑上就是个小根堆了你是怎么倒叙呢 不就是首元素和尾元素交换。
23};SortFF(vv， 堆的分类 大根堆:每个节点的值都大于或者等于他的左右孩子节点的值 小根堆:每个结点的值都小于或等于其左孩子和右孩子结点的值 两种结构映射到数组为: 大根堆: 小根堆: //父--子:i---左孩子:2*i1， len - 1);}//每次将根和待排序的最后一次交换然后在调整int tmp;for (int i 0; i len - 1; i){tmp arr[0];arr[0] arr[len - 1-i];arr[len - 1 - i] tmp;HeapAdjust(arr。
5，9，3。
87，0， int start， 排除已经确定的最大元素将剩下元素重新构建大根堆 一次交换重构如图: 此时元素9已经有序末尾元素则为4( 每调整一次调整后的尾部元素在下次调整重构时都不能动 ) 二次交换重构如图: 最终排序结果: 由此我们可以归纳出堆排序算法的步骤 1. 把无序数组构建成二叉堆，6，1。
pos);//那么就是开始重新调整除过已经确认元素剩下那一段数组元素//这下又把这一段数组里面最小的放在堆顶//再次进入循环去交换位置}}int main(){vectorintvv{53， 那为什么每次交换完需要我尾巴元素不能动去构建剩余元素呢你每构建完一次小根堆交换元素你此时在数组上是不是把最小的元素放在末尾了说明已经确定了那我们就不需要动了我们要动的就是数组那些没确定的元素在这些里面去找一个最小的，那么我们只要反复删除堆顶反复调节二叉堆所得到的集合就成为了一个有序集合 堆排序是不稳定的排序空间复杂度为O(1)， 0， 当我们删除一个最大堆的堆顶并不是完全删除而是替换到最后面经过自我调节第二大的元素就会被交换上来成为最大堆的新堆顶， sizeof(arr) / sizeof(arr[0]));printf(排序后为:);for (int i 0; i sizeof(arr) / sizeof(arr[0]); i){printf(%d 。
最坏情况下也稳定在O(nlogn) 代码示例:void HeapAdjust(int* arr，45， 再提一嘴像数据结构优先队列这种他底层就是按照大根堆的方式去实现的top返回的是最大值排序取出优先级最高的是一个降序队列 补充 理解堆排序他其实就是对于一组数去进行排序(这里放在数组里)而我们所说的大根堆小根堆都是逻辑上的让我们去理解排序算法千万别混为一谈迷糊了 还是这么一组无序的数字我们把它逻辑构造成一个完全二叉树 我们这里按照从大到小排序构建小根堆的大致思路来说 我们堆排序的步骤就是这样 先把这个最初的堆去 给他构建成一个小根堆所谓小根堆就是堆顶元素最小 注意构建的时候就需要我们找分支结点我最上面提到的那数学公式我们从这个分支结点开始把它的父结点这么一个小树弄成小根堆再往上跳从他的父结点开始找双亲把他们这一部分调整成最小堆，2， 堆是一种叫做完全二叉树的数据结构可以分为大根堆小根堆而堆排序就是基于这种结构而产生的一种程序算法，65， 在这里5小于6， pos。
5， int end)//构建最小堆{int i start， i，17。
体现在数组上就是你数组首元素现在是最小的因为你堆顶就代表着0号下标元素不是。
平均的时间复杂度为O(nlogn)，96。
依次类推 说白了就是从下面局部构成小根堆一点一点最后整体全局构建小顶堆， int end){int tmp arr[start];for (int i 2 * start 1; i end; i i * 2 1){if (i end arr[i] arr[i 1])//有右孩子并且左孩子小于右孩子{i;}//i一定是左右孩子的最大值if (arr[i] tmp){arr[start] arr[i];start i;}else{break;}}arr[start] tmp;}void HeapSort(int* arr，我今天就再拿文字和简单的图把思路说一下补充的我按照构建小顶堆就是从大到小排序一组数字。
右孩子:2*i2; //子--父:i---(i-1)/2; ( i为下标元素 ) 排序思想 1.首先将待排序的数组构造成一个大根堆此时整个数组的最大值就是堆结构的顶端 2.将顶端的数与末尾的数交换此时末尾的数为最大值剩余待排序数组个数为n-1 3.将剩余的n-1个数再构造成大根堆再将顶端数与n-1位置的数交换如此反复执行便能得到有序数组 注意:升序用大根堆降序就用小根堆(默认为升序) 构造堆 那么如何构造大根堆呢? 首先我们给定一个无序的序列将其看做一个堆结构一个没有规则的二叉树将序列里的值按照从上往下从左到右依次填充到二叉树中，vv.size());for (auto const x : vv) {cout x ;}return 0;} 就到这里了我用大白话把整个过程描述了一遍 ， int n)//堆排序{//if ( nums.size()0||n 2)return;int pos (((n - 1) - 1) / 2);while (pos 0)//从下往上局部最后整体去调整成小顶堆{FF(nums。
3，4 这么一组数我们第一次构建小根堆之后1就跑到了堆顶也就是跑到了数组首元素1数组此时为1 * * *和最后一个元素交换就成了* * * 1那么这个时候1就已经确定了我们下来要做的是把* * *这三个构建出一个小根堆这三个里最小的放在首元素 比方说是2 * * 1我们交换2和这次没确定的数组最后一个元素成了* * 2 1此时2 和1已经确定了我们再去剩下两个* *去构建去交换最后得到 6 4 2 1 还是这三步 把无序的这一串数想象成一个堆根据要求去从局部到整体构建一个大顶堆或者小顶堆我们要的就是此时这个堆顶元素 把堆顶元素和末尾元素交换就是把堆顶元素数组首元素换到了数组的末端 重新调整除了数组末端(已经确定顺序的元素)以外的元素去构建堆然后交换堆顶和当前末尾构建交换堆顶和当前末尾.. 给个小根堆的测试代码 void FF(vectorint nums，78。
1，而9大于6则交换6和9的位置 找到下一个非叶子节点4用它和它的左右子节点进行比较4大于3而4小于9交换4和9位置 此时发现4小于5和6这两个子节点我们需要进行调整左右节点5和6中6大于5且6大于父节点4因此交换4和6的位置 此时我们就构造出来一个大根堆，那么这一步体现在堆上是不是需要我们重新再除了尾巴元素以外剩下结点上 从局部到整体去构建小根堆了， 对于一个完全二叉树在填满的情况下非叶子节点都有两个子节点每一层的元素个数是上一层的二倍根节点数量是1所以最后一层的节点数量一定是之前所有层节点总数1所以我们能找到最后一层的第一个节点的索引即节点总数/2根节点索引为0这也就是第一个叶子节点所以第一个非叶子节点的索引就是最后一个叶子结点的索引-1， 2. 循环删除堆顶元素移到集合尾部调节堆产生新的堆顶， 再一次构建是不是这里面最小的跑到堆顶了数组里就是最小的跑到了首元素位置再去交换首元素和没有排好序的这一段数组的最后一个下标位置交互完了再重构..... 举个例子6。
len - 1-i- 1);}}int main(){int arr[] { 9， int len){//第一次建立大根堆从后往前依次调整for(int i(len-1-1)/2;i0;i--){HeapAdjust(arr。
nums[pos]);//交换第一个元素和pos指向的位置第一次完了之后最小元素就在数组最后pos-1; //让pos指向数组往前一个位置相当于最后一个元素是最小的已经确认FF(nums， j 2*i1;int tmp nums[i];while (jend){if (j end nums[j] nums[j 1]) j 1;if (tmp nums[j])break;nums[i] nums[j];i j;j i * 2 1;}nums[i] tmp;}void SortFF(vectorintnums， 正如上图所示当我们删除值为9的堆顶节点经过调节值为6的新节点就会顶替上来当我们删除值为6的堆顶节点经过调节值为5的新节点就会顶替上来....... 由于二叉堆的这个特性我们每一次删除旧堆顶调整后的新堆顶都是大小仅次于旧堆顶的节点，n - 1);pos-1;}//调整完了此时这个二叉堆最上面就是最小的数//在数组里就是一顿调整之后第一个元素是最小的pos n - 1;//让pos指向数组最后一个位置while (pos 0){swap(nums[0]，这样构建之后你全局的堆顶才是最小的一个元素 这才是所谓的完整的一次构建，66 };HeapSort(arr。
0， arr[i]);}return 0;} 排序结果: 路过有帮助麻烦点个赞再走博主画图不容易┭┮﹏┭┮ 2022/11/19 补充 这篇文章写的也挺早的了今天抽空重新补充一下因为很多朋友私信我说是没看懂或者怎么样的(写的早文笔表达确实有限)，然后你数组最后面不就成了最小的这是体现在数组上的那么同样体现在此时这个小根堆上就是把堆顶元素和尾巴一交换，那么对于填不满的二叉树呢这个计算方式仍然适用当我们从上往下从左往右填充二叉树的过程中第一个叶子节点一定是序列长度/2 所以第最后一个非叶子节点的索引就是 arr.len / 2 -1对于此图数组长度为5最后一个非叶子节点为5/2-11即为6这个节点 那么如何构建呢 我们找到了最后一个非叶子节点即元素值为6的节点 比较它的左右节点中最大的一个的值是否比他大如果大就交换位置 ，下来进行排序 首先将顶点元素9与末尾元素4交换位置此时末尾数字为最大值。
也有很多朋友问啊大根堆构建出来堆顶是最大的元素你最后排序输出可又是从小到大问出这些问题就说明你没有好好看步骤，。