堆排序理解

发表于： 分类于：
字数：571 阅读：≈ 2分钟 浏览：

堆排序的关键是构建大（小）顶堆，堆顶元素就是最大（小）的元素，然后堆顶元素和末尾元素交换位置，再次堆化除最后一个元素外的其它元素，循环次过程即可完成排序。

翻译成代码如下：

public void sort(int a) {
    for(int i = a.length - 1; i > 0; i--) {
        buildHeap(a, i);
        // 堆顶元素和最后一个元素交换，除过最后一个元素外其它元素再次构建大顶堆
        swap(a, 0, i);
    }
}

堆化过程

1、从序列最后一个非叶子节点开始 2、堆化规则：替换节点为当前节点和叶子节点中值最大的节点 3、倒序依次处理其它非叶子节点 4、须保证叶子节点也满足堆化规则

前置知识

1、堆是完全二叉树 2、满二叉树使用数组存储最省空间 3、若节点在数组中的下标为 n，其左叶子节点在数组中的下标为 2 * n + 1，右子节点下标为 2 * n + 2，父节点下标为 (n - 2)/2

堆化过程图解

堆化过程

翻译成代码如下：

/**
 * 构建大顶堆
 *
 * @param a 数组
 * @param n 最后一个元素下标
 */
public static void buildHeap(int[] a, int n) {
    // 从最后一个非叶子节点开始，倒序依次处理其它非叶子节点
    for(int i = (n -1) / 2; i >=0; i--) {
        heapify(a, n, i);
    }
}

/**
 * 堆化
 *
 * @param a 数组
 * @param n 最后一个元素下标
 * @param i 需要调整的父节点下标
 */
public static void heapify(int[] a,int n, int i) {
    while (true) {
        // 大顶堆规则：替换节点为当前节点和叶子节点中值最大的节点
        int maxPos = i;

        int l = 2 * i + 1;
        if (a[l] > a[maxPos]) {
            maxPos = l;
        }

        int r = 2 * i + 2;
        if (a[r] > a[maxPos]) {
            maxPos = r;
        }

        // 当前节点最大时退出
        if (maxPos == i) {
            return;
        }

        swap(a, maxPos, i);

        // 保证叶子节点也满足堆化规则
        i = maxPos;
    }
}

public static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}