临沂建设企业网站,企业融资计划书范本,提供网站建设空间,遵义网络公司堆排序过程如下#xff1a; 1.用数列构建出一个大顶堆#xff0c;取出堆顶的数字#xff1b; 2.调整剩余的数字#xff0c;构建出新的大顶堆#xff0c;再次取出堆顶的数字#xff1b; 3.循环往复#xff0c;完成整个排序。
构建大顶堆有两种方式#xff1a; 1.从 0 开…堆排序过程如下 1.用数列构建出一个大顶堆取出堆顶的数字 2.调整剩余的数字构建出新的大顶堆再次取出堆顶的数字 3.循环往复完成整个排序。
构建大顶堆有两种方式 1.从 0 开始将每个数字依次插入堆中一边插入一边调整堆的结构使其满足大顶堆的要求 2.将整个数列的初始状态视作一棵完全二叉树自底向上调整树的结构使其满足大顶堆的要求。 二更为常用 void swap(vectorint arr, int i, int j)
{int temp arr[i];arr[i] arr[j];arr[j] temp;}// 调整大顶堆第三个参数表示剩余未排序的数字的数量也就是剩余堆的大小void maxHeapify(vectorint arr, int i, int heapSize) {// 左子结点下标int l 2 * i 1;// 右子结点下标int r l 1;// 记录根结点、左子树结点、右子树结点三者中的最大值下标int largest i;// 与左子树结点比较if (l heapSize arr[l] arr[largest]) {largest l;}// 与右子树结点比较if (r heapSize arr[r] arr[largest]) {largest r;}if (largest ! i) {// 将最大值交换为根结点swap(arr, i, largest);// 再次调整交换数字后的大顶堆maxHeapify(arr, largest, heapSize);}
}// 构建初始大顶堆
void buildMaxHeap(vectorint arr) {// 从最后一个非叶子结点开始调整大顶堆最后一个非叶子结点的下标就是 arr.length / 2-1for (int i arr.size() / 2 - 1; i 0; i--) {maxHeapify(arr, i, arr.size());}
}void heapSort(vectorint arr) {// 构建初始大顶堆buildMaxHeap(arr);for (int i arr.size() - 1; i 0; i--) {// 将最大值交换到数组最后swap(arr, 0, i);// 调整剩余数组使其满足大顶堆maxHeapify(arr, 0, i);}
}
