当前位置: 首页> 游戏> 游戏 > 域名138查询网_东莞网站制作与网站建设_抖音关键词排名优化_西安竞价托管

域名138查询网_东莞网站制作与网站建设_抖音关键词排名优化_西安竞价托管

时间:2025/7/12 0:03:00来源:https://blog.csdn.net/softstarhhy/article/details/146375340 浏览次数:0次
域名138查询网_东莞网站制作与网站建设_抖音关键词排名优化_西安竞价托管

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点.

先上代码 

public class HeapSort {void  heapSort(int A[]){if (A == null || A.length <= 1) {return;}int n = A.length;// 1. 构建最大堆(从最后一个非叶子节点开始)for (int i = (n - 1) / 2; i >= 0; i--) {heapify(A, n, i);}// 2. 进行堆排序for (int i = n - 1; i >= 0; i--) {swap(A, 0, i);  // 交换堆顶和最后一个元素heapify(A, i, 0);  // 重新调整堆}}// 调整堆(维护堆的性质)private void heapify(int[] A, int heapSize, int parentIndex) {int largest = parentIndex;int leftChild = 2 * parentIndex + 1;int rightChild = 2 * parentIndex + 2;// 检查左子节点if (leftChild < heapSize && A[leftChild] > A[largest]) {largest = leftChild;}// 检查右子节点if (rightChild < heapSize && A[rightChild] > A[largest]) {largest = rightChild;}// 如果最大值发生变化,交换并递归调整if (largest != parentIndex) {swap(A, parentIndex, largest);heapify(A, heapSize, largest);}}// 交换两个数组元素private void swap(int[] A, int i, int j) {int temp = A[i];A[i] = A[j];A[j] = temp;}
}

以数组A = {4, 6, 8, 5, 9}为例 

在其调整之后 

        9
       /   \
      6     8   调整后变为                           
     / \
    5   4                          

         4
       /   \
      6     8
     / 
    5   9 (已排序) 那么首先第一个问题便是

为什么不能直接使用 heapAdjust(A, n, 0); 来构建大顶堆,而是要用 for(int i = (n-1)/2; i >= 0; i--) heapAdjust(A, n, i);

只对 heapAdjust(A, n, 0); 进行一次调用,它仅调整 A[0] 这一棵子树,但不会处理整个数组形成的堆结构,导致并不是所有子树都符合最大堆的定义

构建大顶堆需要同时满足左子树和右子树小于堆顶的元素 若从A[0]开始进行遍历 并且开始递归 只能保证一侧的子树满足要求 而不能保证左子树和右子树同时满足 因为堆排序是类似于完全二叉树的结构 所以需要进行从最后一个非叶子节点 i = (n-1)/2 开始,依次向上调整堆,保证每个子树都符合最大堆的定义,最终整个数组成为一个合法的最大堆.

那么又会有第二个问题

进行堆调整 for(int j=n-1;j>=0;j--)

{ swap(A,j,0);

heapAjust(A,j,0);

}堆调整只需要从0开始呢而不是从 j/2 开始呢

删除堆顶(交换 A[0] 和 A[j]) 之后,A[0] 可能不再是最大值,需要调整。 但 堆的其他部分(A[1] ~ A[j-1])仍然是最大堆,只有 A[0] 可能破坏堆结构。 只需要让 A[0] 向下调整,恢复最大堆。

只需要 heapAdjust(A, j, 0); 只让 A[0] 下沉,保持 A[0] ~ A[j-1] 的最大堆性质。

这比 for (int i = j/2; i >= 0; i--) 更高效,因为只用调整 A[0],不需要重新遍历整个堆 那也就是说 如果交互从i=j/2也没有错 只不过是多加计算了 没有任何意义 没有调整的一侧根本不需要改变 因为在构建堆的时候已经比较过了 即调整的意义在于不会遍历整个堆 只会让堆的一侧进行运算 因为只修复 A[0],不影响其他节点 所以不可能访问所有的非叶子节点  即最优解是最优解是 heapAdjust(A, j, 0);

关键字:域名138查询网_东莞网站制作与网站建设_抖音关键词排名优化_西安竞价托管

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: