(从零开始讲,一步一步)大根堆-＞下沉上浮-＞堆排序-＞优化代码

零 前言(从零开始讲,一步一步)大根堆-下沉上浮-堆排序-优化代码内容有点多建议先看一下目录哈代码都AC了没有最强的数据结构 只有适应应用场景的最优解法一 heapInsert()给一个大根堆数组arr 和 一个数值val把它插入数组 使数组仍然是大根堆1 代码实现voidheapInsert(vectorintarr,intval){intiarr.size();arr.push_back(val);//直接插入在后面while(i0arr[(i-1)/2]arr[i]){//不断循环的看arr[i]的父亲是否arr[i]swap(arr[(i-1)/2],arr[i]);//arr[i]大就交换i(i-1)/2;//i来到新位置}return;}2 这样更易读voidheapInsert(vectorintarr,intval){intiarr.size();arr.push_back(val);while(true){intpar(i-1)/2;//父亲节点if(i0||arr[par]arr[i])break;//如果i已经是根节点或者父亲节点当前节点swap(arr[par],arr[i]);ipar;}}二 heapify()先从简单的开始0位置的值变为val了 重新调整为大根堆0位置的数据被换为val1 分析思路一定要向下调整(总不能往上吧 上面没有数据)要保证是大根堆 就必须保证每一个子树的根节点必须是最强的值需要找到 左孩子 右孩子 中最大值 (如果没有左孩子 右孩子 已经到叶子节点了 不用循环往下走了 )(如果没有右孩子 只有左孩子 左右孩子的最大值就是左孩子的值 )左孩子下标lefti*21;intbestleft;//当前最大孩子是左孩子 best是下标if(left1arr.size()){//就是存在右孩子if(arr[best]arr[left1]){//如果右孩子的值更大 更新bestbestleft1;}}//这样我们就找到了左右孩子中最大的下标之后需要和arr[i] 比较 (就是和自己比较)如果arr[i]arr[best] 说明自己就是那个最大值 不用再往下沉了 就是这位置如果arr[i]arr[best] 说明不满足大根堆的条件 需要往下沉 具体就是swap(arr[i],arr[best]);ibest;2 代码实现(标准简洁版)//AC了voidheapify(vectorintarr,inti,intval){//i0arr[i]val;//i位置的值调整为val//之后要向下调整intli*21;//左孩子//如果没有左孩子 一定也没有右孩子 说明是大根堆叶子节点了 后面没有数据了 不进入循环while(larr.size()){//有左孩子 进入循环intbestl;//best是最大的那个孩子的下标//下面我要找最强孩子(就是最大孩子)if(l1arr.size()){//如果有右孩子bestarr[l]arr[l1]?l:l1;//比较一下当前最强孩子和右孩子 决定要不要更新}if(arr[best]arr[i])break;//三者之中最强是我自己i 不用再往下了 这个i就是自己的位置swap(arr[best],arr[i]);//最强孩子不是我自己 必须我往下走了ibest;//i是我的位置 更新li*21;//新的左孩子 因为当没有左孩子的时候 就是指是大根堆叶子节点的时候要结束循环}return;}3 这样会不会更易读(易读版)voidheapify(vectorintarr,inti,intval){//i0arr[i]val;while(true){intlefti*21;//左孩子if(leftarr.size())break;//如果连左孩子都没有 说明到了叶子节点位置intbestleft;//当前左右孩子中最大的孩子下标为bestleftif(left1arr.size()){//如果存在右孩子 需要判断是否更新bestif(arr[best]arr[left1])bestleft1;//右孩子更大 bestright(就是left1)}//经过上面的操作已经找到了best//best就是最大的孩子的下标 arr[best]就是最大孩子的值if(arr[i]arr[best]){//如果自己就是最大值 不用再往下沉了 就是这个位置 (列强竟是我自己 哈哈哈)break;}//如果自己不是最大值 需要往下沉 执行下面操作swap(arr[i],arr[best]);//交换值ibest;//i来到best位置}return;}进阶如果在一个大根堆中有一个位置 i 的元素被替代为val请调整为大根堆这个问题需要分两种情况原来的值为original如果originalval 不用管了直接就是大根堆如果original val 需要向下调整(下沉) (因为原来上面的值都是大于original的 val又是小于original的 所以上面的值都是大于val的 不需要向上调整 )如果original val 需要向上调整(上浮) (因为原来下面的值都是小于original的 val又是大于original的 所以下面的值一定是小于val的 不需要向下调整)三 堆排序O( nlogn )1 排序思路先建立大根堆(因为大根堆的根节点一定是数组的最大值)建立大根堆的过程可以有两种方法一 方法二方法一: 自底向上每一个arr[i]都下沉方法二: 从顶向下每一个元素都上浮建立大根堆之后交换arr[0]和最后一个元素 相当于 最后一个位置就排好序了 之后我们忽略最后一个元素 对交换了之后的数组 进行0位置的下沉 这样这个数组又变成了大根堆 再交换arr[0]和最后一个元素 重复操作2 代码实现voidsiftUp(vectorintarr,inti){//对数组arr的i位置上浮while(true){intpar(i-1)/2;if(i0||arr[par]arr[i])break;swap(arr[par],arr[i]);ipar;}return;}voidsiftDown(vectorintarr,intn,inti){//数组的长度为n 对i位置的元素下沉while(true){intlefti*21;if(leftn)break;intbestleft;if(left1narr[left1]arr[best])bestleft1;if(arr[i]arr[best])break;//当前节点的值已经最大的左右孩子的值 就是到达正确位置了//下面执行下沉操作swap(arr[best],arr[i]);ibest;}return;}voidheapSort01(vectorintarr){//首先建立大根堆//方法一 从前往后元素上浮//方法二 从后往前元素下沉for(inti0;iarr.size();i){//方法一siftUp(arr,i);}for(intiarr.size()-1;i0;--i){//变为大根堆后arr[0]是最大值 将它和arr最后一个元素交换swap(arr[i],arr[0]);//对0位置的元素下沉 又变为了大根堆siftDown(arr,i,0);}return;}3 代码优化建大根堆时 采用自底向上的方式(这样更好 应为叶子节点的位置不用siftDown 直接就ok了)(详细说就是差不多有n/2的规模是只用往下沉一层就行了差不多有n/4的规模是只用往下沉两层就行了…)反过来如果用 自顶向上建堆的话 最后一层节点要经历的层数多并且叶子节点的数量有很多 承担的代价太大voidheapSort02(vectorintarr){for(intiarr.size()-1;i0;--i){siftDown(arr,arr.size(),i);}for(intiarr.size()-1;i0;--i){swap(arr[i],arr[0]);siftDown(arr,i,0);}return;}