当前位置：首页 > article >正文

堆排序的思路与常见的问题

article 2025/3/20 23:35:43

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

先上代码

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);

查看全文

http://www.kler.cn/a/593198.html