Java 堆排序原理 图文详解 代码逻辑

1. 时间复杂度 & 空间复杂度

• 时间复杂度: O(nlogn)
  建堆时间复杂度: O(n)
  排序时间复杂度: O(nlogn)
• 空间复杂度: O(1)

2. 大顶堆、小顶堆

现有堆排序 分为大顶堆 和 小顶堆, 本文以大顶堆为例.

• 大顶堆: 所有节点的父节点均大于左右孩子节点
  9 大于 7 、8
  9的左孩子7, 大于其左右孩子 5 6
  9的右孩子8, 大于其左右孩子 3 4
  7的左孩子 5, 大于其左右孩子 1 2
  
  前序遍历结果为: 9 7 8 5 6 3 4 1 2
• 小顶堆: 所有节点的父节点均小于左右孩子节点
  1 的左右孩子 2 3, 均大于1
  1 的左孩子 2 , 其左右孩子 4 5 均大于2
  1 的右孩子 3 , 其左右孩子 6 7 均大于3
  2 的左孩子 4 , 其左右孩子 8 9 均大于4
  
  前序遍历结果: 1 2 3 4 5 6 7 8 9

3. 具体步骤 & 原理

当我们需要对一个无序数组进行排序时, 使用堆排序往往是一个不错的选择. 时间复杂度和空间复杂度相比冒泡、快排等均有不同程度的提升.
加入我们想要对以下数据排序, 其具体步骤及原理如下

前序遍历结果: 3 5 4 7 1 2 9 6 8

1. 判断是否满足堆的性质

当我们拥有一个无序数组后, 每次去判断是否满足 大顶堆 或 小顶堆 的性质, 这里选择用大顶堆.
因为 大顶堆 需要满足条件: 父节点比左右孩子节点大, 我们从根节点开始遍历, 确认是否满足.

从图中可以看到 3 5 4不满足 根节点大于左右孩子节点. 这怎么办呢?

2. 维护堆的性质

此时就需要我们去做交换, 从左右孩子中找到最大的那个节点, 并与根节点做交换.

1. 我们发现, 5 在这三个数中最大, 就让他与3交换, 得到第一步结果:
   
2. 根节点交换后, 我们继续遍历左右孩子节点, 判断是否满足大顶堆性质
   
   发现 3 的左右孩子节点 7 1 并不满足大顶堆性质, 继续交换得到结果 7 3 1
   
3. 交换完后我们发现根节点与左右孩子 变为了 5 7 4, 不再满足大顶堆性质了
   
   继续交换 5 和 7, 得到7 5 4
   
4. 此时继续遍历 7的左子结点 5 的 左右孩子 5 3 1, 发现满足条件, 继续遍历5的左子结点 3
   
5. 3 的左右孩子结点 6 8 不满足大顶堆性质, 继续交换 3 和 8
   
6. 接着继续遍历, 直到所有的节点均满足 大顶堆 性质为止
   5 8 1不再满足大顶堆性质, 继续交换8 和 5
   
   遍历7 8 4, 不满足条件, 交换 7 和 8
   
   此时7 5 1 满足条件, 继续遍历7的左子结点5, 看他的左右孩子节点是否满足条件.
   遍历5 6 3, 不满足条件, 继续交换 5 和 6, 得到 6 5 3
   
   遍历4 2 9, 不满足条件, 交换4 和 9, 得到9 2 4
   
   遍历 8 7 9, 不满足条件, 交换8 和 9
   
   最终, 得到了结果 9 7 8 6 1 2 4 5 3, 这个就是第一次遍历后得到的最终结果.

3. 交换位置

从结果中我们发现: 根节点值最大,并且满足每一个父节点均大于左右孩子节点. 此时的结果就是一个 大顶堆

1. 接下来, 我们只需要将 根节点值与 最后一个值 交换.可以得到 3 7 8 6 1 2 4 5 9
   

2. 这时, 最大的数字放到了最后, 我们就完成了初步交换, 接着我们将 9 剔除, 9不再参与 堆性质的维护.
   

3. 从3开始, 继续维护堆的性质, 并且交换位置, 最终得到如下结果: 8 7 4 6 1 2 3 5
   

4. 继续交换根节点和最后一个节点的位置, 得到5 7 4 6 1 2 3 8
   

5. 将8 剔除, 并且重复以上步骤, 得到了最终结果 1 2 3 4 5 6 7 8 9
   

6. 这样子我们就得到了最终排序后的结果

4. 代码实现

public static void main(String[] args) {
    int[] nums = new int[]{3,5,4,7,1,2,9,6,8};
//        int[] nums = new int[]{-4,0,7,4,9,-5,-1,0,-7,-1};
    heapSort(nums, nums.length);
    for (int num : nums) {
    	// 1 2 3 4 5 6 7 8 9
        System.out.println(num);
    }
}

/**
 * 维护堆的性质
 * @param nums 数组
 * @param len 数组长度
 * @param i 数组下标
 */
public static void heapify(int[] nums, int len, int i) {
    // 根节点的下标
    int largest = i;
    // 左子结点下标
    int l = 2 * i + 1;
    // 右子节点下标
    int r = 2 * i + 2;
    // 判断 左子节点 的值 是否大于 根节点的值, 如果大于, 则交换位置
    if (l < len && nums[l] > nums[largest]) {
        largest = l;
    }
    // 判断 右子节点 的值 是否大于 根节点的值, 如果大于, 则交换位置
    if (r < len && nums[r] > nums[largest]) {
        largest = r;
    }
    // 如果根节点的下标发生了变化, 则进行交换位置
    if (largest != i) {
        // 交换位置
        swap(nums, largest, i);
        // 递归维护堆的性质
        heapify(nums, len , largest);
    }
}

/**
 * 构建堆 & 排序
 * @param nums
 * @param len
 */
public static void heapSort(int[] nums, int len) {
    // 下标为i的左子结点
    for (int i = (len - 1) / 2; i >= 0; i--) {
        heapify(nums, len, i);
    }

    // 循环遍历, 交换根节点 与 最后一个节点 位置
    for (int i = len - 1; i > 0; i--) {
        swap(nums, 0, i);
        // 维护堆的性质
        heapify(nums, i, 0);
    }
}

/**
 * 交换位置
 * @param nums
 * @param l
 * @param r
 */
public static void swap(int[] nums, int l, int r) {
    int tmp = nums[l];
    nums[l] = nums[r];
    nums[r] = tmp;
}