堆排序图解(算法原理及Java代码实例)

堆排序是Java排序比较重要的一种，本文会以详细介绍堆排序的基本思想及其代码实现@mikechen

堆排序定义

堆排序，英文名为Heap Sort，是将数据看成近似完全二叉树结构，并根据完全二叉树的特性来进行排序的一种算法。

堆排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。

 

堆排序方法

堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点，通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组。

堆排序可以说是一种利用堆的概念来排序的选择排序，分为两种方法：大顶堆、小顶堆。

1.大顶堆

每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，如下图所示：

2.最小堆

每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆，如下图所示：

 

 

堆排序基本思想

堆排序的基本思路，主要分为如下3步：

1）首先：数据按照二叉数来看待，将其下标与二叉树节点对应起来；

2）其次：构建最大堆（Build-Max-Heap），将堆所有数据重新排序，使其成为最大堆，并且冒出最大数；

3）最后：堆排序(Heap-Sort)，从最后一个子节点开始遍历，并将根节点与其交换，也就是移除第一个数据的根节点，并做最大堆调整的递归调用，直到排序完成。

 

堆排序图解

上面我们理解了大致的思路，下面我们看一个动图就会更加清楚。

下图所示：

排序的详细过程，如下：

 

堆排序代码案例

上面我们了解了思路与原理，下面我们具体编程程序来实现。

代码如下：

public class HeapSort {
 
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组不能为空");
            return;
        }
 
        /*
         * 大顶堆的是一个完全二叉树，所以最后的非叶子节点开始到根节点，每个节点都是非叶子节点。
         * 下面for循环将一个无序的二叉树构建成了大顶堆。从最后一个非叶子节点(arr.length / 2 - 1 )
         * 开始，直到根节点0，是一个树结构上从右到左，从下而上构建大顶堆的过程。
         * 因为自下而上构建，所以，当父节点比左右子节点大的时候，不用再遍历左右子节点的子节点了。
         */
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
 
        System.out.println("排序后=" + Arrays.toString(arr));
        /*
         * 注意下面这个循环每次调用adjustHeap()时，因为末尾元素和堆顶元素交换了位置，正好被破坏了，
         * 千万注意，目前的这个被破快的结构是除了堆顶元素下面的分支都是符合大堆顶的二叉树。
         * 现在只需要从上而下，将交换过来的栈顶元素放到一个合适位置就好了。
         * adjustHeap()的做法就是，从堆顶元素开始找到左右子节点中较大的数，和堆顶元素比较，如果比堆顶元素大，就替换元素，
         * 如果没有堆顶元素大，正好符合大顶堆的要求（解释了方法中break的由来），如此循环，不断调整结构，使其满足堆定义，
         * 给堆顶元素找到合适的位置。
         */
        for (int n = arr.length - 1; n > 0; n--) {
            System.out.println("剩余数据量为" + (n + 1));
            int temp = arr[n];
            arr[n] = arr[0];
            arr[0] = temp;
            System.out.println("排序后=" + Arrays.toString(arr));
            adjustHeap(arr, 0, n);
            System.out.println("调整后=" + Arrays.toString(arr));
        }
    }
    //将一个根节点索引为i的子二叉树，调整成一个大顶堆
    /**
     * @param arr 待调整的数组
     * @param i 表示非叶子结点在数组中索引
     * @param lenght 表示对多少个元素继续调整， length 是在逐渐的减少
     */
    private static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        //1. k = i * 2 + 1 k 是 i结点的左子结点
        for (int j = i * 2 + 1; j < length; j = j * 2 + 1) {
            //说明左子结点的值小于右子结点的值。j指向右节点。本质就是找到左右节点中的较大值
            if (j + 1 < length && arr[j] < arr[j + 1]) {
                j++;
            }
            //如果子结点大于父结点
            if (arr[j] > temp) {
                //把较大的值赋给当前结点
                arr[i] = arr[j];
                //!!! i 指向 k,继续循环比较
                i = j;
            } else {
                /*
                 * 下面break的理解至关重要。上面调用方法两次提到这里！注意看上面解释！
                 */
                break;
            }
        }
        //当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)。并且给temp找到了合适为位置(当前i的位置)
        arr[i] = temp;
    }
 
public static void main(String[] args) {
        // 要求将数组进行升序排序
        int arr[] = { 7, 4, 3, 8, 9, 10, -1, 99 };
        System.out.println("排序前=" + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("最终结果=" + Arrays.toString(arr));
    }
}