福田网站设计公司哪家好,保定网站建设设计公司,凡科网登录下载,微信网站建设咨询“留在码头的船才最安全” “但亲爱的#xff0c;那不是造船的目的。 堆--插入heapInsert
原来有一个大根堆#xff0c;如图#xff1a; 现在要新插入一个数字50#xff0c;进行插入 流程#xff1a;和父亲相比#xff0c;如果比父亲大#xff0c;和父亲交换#xff… “留在码头的船才最安全” “但亲爱的那不是造船的目的。 堆--插入heapInsert
原来有一个大根堆如图 现在要新插入一个数字50进行插入 流程和父亲相比如果比父亲大和父亲交换直到不比父亲大或者来到0位置
void heapInsert(vectorint arr, int i) {while (arr[i] arr[(i - 1) / 2]) {swap(arr[i], arr[(i - 1) / 2]);i (i - 1) / 2;}
}插入50 50比13大交换 50比20大交换 50比40大交换 调整成功 由于完全二叉树有n个节点会有logn深度因此插入的时间复杂度是O(logn)
堆调整 heapify
还是上面的那个例子想把0位置的40改为4此时破坏了大根堆的性质如何调整 假设当前下标为i如果i位置有左孩子和右孩子则左孩子的下标为li*21右孩子为l1 左右孩子比较出最大的孩子 最大的孩子和当前数字比较如果孩子大那么交换如果是自己大那么不动 4和20交换 4和13交换 堆调整完成时间复杂度O(logn)
void heapify(vectorint arr, int i, int size) {//可能没有左孩子int l i * 2 1;//左孩子下标while (l size) {//有左孩子//右孩子l1//评选左右孩子的最强的孩子下标是什么//1次比较int best l 1 size arr[l 1] arr[l] ? l 1 : l;//上面已经选最强的孩子接下来当前的数字和最强的孩子之前最强下标是谁//2次比较best arr[best] arr[i] ? best : i;if (best i) {break;//最强的是自己不用向下调整了}//最强孩子比自己更强swap(arr[best], arr[i]);i best;l i * 2 1;}
}
堆排序 从顶到底建立堆的时间复杂度是O(nlogn) 大数归为的时间复杂度是O(nlogn) 因此总时间复杂度O(nlogn)
void heapInsert(vectorint arr, int i) {while (arr[i] arr[(i - 1) / 2]) {swap(arr[i], arr[(i - 1) / 2]);i (i - 1) / 2;}
}
void heapify(vectorint arr, int i, int size) {//可能没有左孩子int l i * 2 1;//左孩子下标while (l size) {//有左孩子//右孩子l1//评选左右孩子的最强的孩子下标是什么//1次比较int best l 1 size arr[l 1] arr[l] ? l 1 : l;//上面已经选最强的孩子接下来当前的数字和最强的孩子之前最强下标是谁//2次比较best arr[best] arr[i] ? best : i;if (best i) {break;//最强的是自己不用向下调整了}//最强孩子比自己更强swap(arr[best], arr[i]);i best;l i * 2 1;}
}void heapsort1(vectorint arr) {//1.建堆int n arr.size();for (int i 0;i n;i) {heapInsert(arr,i);}//2.大数归位int size n;while (size 1) {swap(arr[0], arr[--size]);//0位置的数字和最后一个交换heapify(arr, 0, size);//再调整0位置这个数字}
}从底到顶建堆时间复杂度是O(n),会比自顶向底快一点但总的时间复杂度不变都是O(nlogn) 大数归为的时间复杂度是O(nlogn) 因此总时间复杂度O(nlogn)
void heapify(vectorint arr, int i, int size) {//可能没有左孩子int l i * 2 1;//左孩子下标while (l size) {//有左孩子//右孩子l1//评选左右孩子的最强的孩子下标是什么//1次比较int best l 1 size arr[l 1] arr[l] ? l 1 : l;//上面已经选最强的孩子接下来当前的数字和最强的孩子之前最强下标是谁//2次比较best arr[best] arr[i] ? best : i;if (best i) {break;//最强的是自己不用向下调整了}//最强孩子比自己更强swap(arr[best], arr[i]);i best;l i * 2 1;}
}void heapsort2(vectorint arr) {int n arr.size();for (int i n - 1;i 0;i--) {heapify(arr, i, n);}//2.大数归位和heapsort1一样的代码int size n;while (size 1) {swap(arr[0], arr[--size]);heapify(arr, 0, size);}
}
