堆排序算法详解、及Java实现

堆排序

需要提前掌握：二叉树、顺序存储二叉树

概述

堆：堆可以看做是一个完全二叉树

大顶堆：其父节点总是大于等于子节点的值，而左右子节点之间没有大小顺序要求

小顶堆：其父节点总是小于等于子节点的值，而左右子节点之间没有大小顺序要求

堆排序：是指利用堆这种数据结构所设计的一种排序算法。以大顶堆为例，我们知道：完全二叉树可以以顺序方式存入数组中的，而大顶堆的根节点是堆中最大的数据，则可以将根节点和最后一个元素交换，再忽略其存在，将前面的元素再次构建成大顶堆，如此反复即可完成排序。

一般，升序采用大顶堆，降序采用小顶堆

实现思想：

1. 将待排序数组构造成一个大顶堆
2. 此时，数组中的最大值就是堆顶的根节点，将其与末尾元素进行交换，此时末尾为最大值
3. 然后将剩余的n - 1个元素重新构造成一个大顶堆，这样对得到一个n个元素中的次小值
4. 如此反复，则可以得到一个有序序列

实现方法

首先要构建一个大顶堆：从最后一个不是叶子的节点开始，比较其与左右子节点的大小。然后一直向右，向上，重复比较操作即可得到一个大顶堆。

然后将根节点和最后一个元素交换位置，之后忽略此最大元素，再从交换后的根节点，循环将前面的元素构建成大顶堆。再交换再构建，如此反复。

我对堆排序的理解、和代码实现都参考了这篇博客，很详细可以看一看：点击查看堆排序图文详解

我的代码中也给出了详细的注释，可以帮助理解

实现代码

package sort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] array = {4,6,8,5,9};
//        adjustHeap(array, 1, 5);
//        System.out.println(Arrays.toString(array));
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }
    public static void heapSort(int[] array){
        //从倒数第一个非叶子节点开始（array.length/2 - 1为其下标）
        // 每次-1，即为二叉树从右至左，从下至上循环
        for (int i = array.length/2 - 1; i >= 0 ; i--) {
            adjustHeap(array, i, array.length);
        }
        //循环到这里即为构建完成大顶堆
        //接下来要将堆顶元素和末尾的叶子节点交换位置
        //然后忽略这个元素，继续对前面的元素构建大顶堆
        for (int i = array.length-1; i > 0; i--) {
            swap(array, 0, i);
            adjustHeap(array, 0, i);
        }
    }
    /**
     *
     * @param array 要操作的顺序二叉树存放的数组
     * @param i 当前节点（父节点）的下标
     * @param length 数组 要操作部分 的长度
     */
    
    public static void adjustHeap(int[] array, int i, int length){
        int temp = array[i];//保存当前节点的值
        //这个方法不是要直接将大顶堆构建完成，而是判断其中的子树的左右节点和父节点的大小，并完成交换
        //而循环的目的则是，此子树完成了交换后，还可能下面的子树父节点比左右子节点小，因此需要循环比较
        //从当前节点的左子节点开始，下标为 i*2+1，i是父节点的下标
        for (int j = i*2+1; j <length ; j = j*2+1) {
            //比较左右节点，右节点大的时候，将下标+1，因为右节点的下标为i*2+2
            if (j+1 < length && array[j] < array[j+1]){
                j++;
            }
            //如果子节点大于父节点，则把子节点的值赋给父节点，无须交换，因为temp保存了这个值
            //而接下来，还需要再进行for循环向下比较temp的值与左右节点的值，
            //每次交换的时候都让i指向它的左子节点，用来和temp比较，
            //最终，i一定指向的是交换完成时，子节点都比自己小的那个节点
            //此时，在for循环结束的时候，将temp的值赋给i下标的值即可
            //此处可能比较难以理解，可以debug调试、或者在草稿纸上模拟一遍，可以帮助理解
            if (array[j] > temp){
                array[i] = array[j];
                i = j;
            } else {
                //如果子节点小于父节点则直接跳出循环即可
                //因为构建大顶堆是从最后一个非叶子节点开始的，而其最多只有两个叶子节点
                //所以比较发现子节点小于父节点，则可以直接跳出循环，换一个父节点继续循环，
                //换父节点的操作是在排序方法中完成
                break;
            }
        }
        array[i] = temp;
    }
    public static void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}