乐趣区

关于java:图解堆排序带你彻底了解清楚

jiezi

写在后面：

大家好，我是时光。

明天给大家带来的是排序算法中的堆排序，这种排序跟二叉树相干。
我采纳图解形式解说，争取写透彻。话不多说，开始！

思维导图：

1，堆排序概念

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

相干概念：

1.1，二叉树

特色：每个节点最多只有 2 个子节点（不存在度大于 2 的节点）

1.2，满二叉树

满二叉树：
叶子节点全副都在最底层；
除叶子节点外，每个节点都有左右孩子；

1.3，齐全二叉树

齐全二叉树：
叶子节点全副都在最底的两层；
最初一层只短少左边的叶子节点，右边肯定有叶子节点；
除了最初一层，其余层的节点个数均达到最大值；

1.4，最大堆和最小堆

最大堆：堆顶是整个堆中 最大元素

最小堆：堆顶是整个堆中 最小元素

2，算法思路

咱们先搞清楚这个堆排序思维，先把逻辑搞清楚，不焦急写代码。

咱们首先有一个无序数组，比方说

int[] arr={4,2,8,0,5,7,1,3,9};

既然用到堆，必定先要将数组构建成二叉堆。须要对数组从小到大排序，则构建成最大堆；须要对数组从小到大排序，则构建成最小堆。

2.1，第一个步骤，初始化堆

咱们先来看看数组是如何存储二叉树的

留神：这里思考的以后节点，必须是齐全二叉树的 非叶子节点。并且节点的左孩子和右孩子必须小于数组长度，所以前面须要增加限度条件。

看到上图中的公式，咱们明确了数组是能够存储齐全二叉树，同时保留节点之间的关系。以上述数组为例

那么存储好之后，如何将二叉树构建成二叉堆呢？持续往下看

以这个图为例，咱们以最大堆举例，若要构建二叉堆，则 A 要比 B 和 C 都大，B 要比 D 和 E 都大，C 要比 F 和 G 都大。也就是说父节点要比子节点都大才行。

在这个图中，显著不满足最大堆的要求。咱们先拿序号为 3,7,8 的三个节点来钻研，i= 3 的节点比 i = 7 和 i = 8 的节点都小，所以须要替换地位。留神此图是从 0 开始，也就是模仿数组下标从 0 开始。

怎么替换呢？很简略。咱们看节点 0，设为以后节点index，那么它的lchild=index*2+1，它的rchild=index*2+2；留神下标从 0 开始。

// 初始化堆
public static void HeapAdjust(int[] arr,int index,int len){
        // 先保留以后节点的下标
        int max = index;
        // 保留左右孩子数组下标
        int lchild = index*2+1;
        int rchild = index*2+2;
        // 开始调整，左右孩子下标必须小于 len，也就是确保数组不会越界
        if(lchild<len && arr[lchild] > arr[max]){max=lchild;}
        if(rchild<len && arr[rchild] > arr[max]){max=rchild;}
        // 若产生了替换，则 max 必定不等于 index 了。此时 max 节点值须要与 index 节点值替换，下面替换索引值，这里替换节点值
        if(max!=index){int temp=arr[index];
            arr[index]=arr[max];
            arr[max]=temp;
            // 替换完之后须要再次对 max 进行调整，因为此时 max 有可能不满足最大堆
            HeapAdjust(arr,max,len);
        }
    }

下面代码很好了解，两头的两个 if 语句就是替换节点索引值，只有有一个孩子节点大于 index，就须要进行替换。若父节点index 比两个孩子节点都大，那么就不须要替换了。

最初面的 if 语句是替换节点值，咱们晓得，只有 index 与lchild和 rchild 有替换，则 index 肯定不等于 max 了！

那为什么最初的 if 语句外面还要加上一个递归写法呢？咱们举个例子就明确了，还是以上述数组为例，先看看一轮替换之后的样子：

第一次替换，0 与 9 替换，此时 Index=9；

第二次替换，8 曾经比 7 和 1 都大了，此时不须要替换；

第三次替换，2 与 9 替换，此时Index=9；

第四次替换，4 与 9 替换，此时Index=9，第一轮替换到此结束。

一轮完结后，有小伙伴儿曾经发现问题了，尽管 9 胜利的成为最大堆的堆顶元素，然而上面的其余元素并不满足最大堆的要求，比如说左下角的元素 2, 元素 3, 元素 0 等这种二叉树就不满足，元素 4，元素 2，元素 5 也不满足。

因而在替换节点值这个步骤里，咱们须要进行递归操作，替换完之后再次对 index 进行堆调整：

// 若产生了替换，则 max 必定不等于 index 了。此时 max 节点值须要与 index 节点值替换，下面替换索引值，这里替换节点值
if(max!=index){int temp=arr[index];
    arr[index]=arr[max];
    arr[max]=temp;
    // 替换完之后须要再次对 max 进行调整，因为此时 max 有可能不满足最大堆
    HeapAdjust(arr,max,len);
}

堆排序的测试：

// 堆排序
    public static int[] HeapSort(int[] arr){
        int len=arr.length;
        /**
         * 第一步，初始化堆，最大堆，从小到大
         * i 从齐全二叉树的第一个非叶子节点开始，也就是 len/2- 1 开始(数组下标从 0 开始)
         */
        for(int i=len/2-1;i>=0;i--){HeapAdjust(arr,i,len);
        }
        // 打印堆顶元素，应该为最大元素 9
        System.out.println(arr[0]);
        return arr;
    }

上述代码就是从齐全二叉树的第一个非叶子节点开始调换，还顺便打印堆顶元素，此时应为 9；

至此，第一个步骤，初始化堆实现，最初的后果应该为下图：

2.2，第二个步骤，堆排序

堆排序的过程就是将堆顶元素（最大值或者最小值）与二叉堆的最开端叶子节点进行调换，不停的调换，直到二叉堆的程序变成从小到大或者从大到小，也就实现了咱们的目标。

咱们这里以最大堆的堆顶元素（最大元素）为例，最初调换的后果就是从小到大排序的后果。

第一次替换，咱们间接将元素 9 与元素 0 替换，此时堆顶元素为 0，设以后节点index=0；

这时，咱们须要将剩下的元素（排除元素 9）进行堆排序，直到上面这个后果：

代码：

/**
 * 第二步，替换堆顶（最大）元素和二叉堆的最初一个叶子节点元素。目标是替换元素
 * i 从二叉堆的最初一个叶子节点元素开始，也就是 len- 1 开始(数组下标从 0 开始)
 */
for(int i=len-1;i>=0;i--){int temp=arr[i];
    arr[i]=arr[0];
    arr[0]=temp;
    // 替换完之后须要从新调整二叉堆，从头开始调整，此时 Index=0
    HeapAdjust(arr,0,i);
}

留神：这里有个小细节问题，后面咱们写的初始化堆办法有三个参数，别离是数组 arr，以后节点index 以及数组长度len，如下：

HeapAdjust(int[] arr,int index,int len)

那么，为何不间接传入两个参数即可，数组长度间接用 arr.length 示意不就行了吗？初始化堆的时候是能够，然而前面在替换堆顶元素和开端的叶子节点时，在对剩下的元素进行排序时，此时的数组长度可不是 arr.length 了，应该是变动的参数i，因为替换之后的元素（比方 9）就不计入堆中排序了，所以须要 3 个参数。

咱们进行第二次替换，咱们间接将元素 8 与元素 2 替换，此时堆顶元素为 2，设以后节点index=2；

这时，咱们须要将剩下的元素（排除元素 9 和 8）进行堆排序，直到上面这个后果：

到这个时候，咱们再反复上述步骤，一直调换堆顶和最开端的节点元素即可，再一直地对剩下的元素进行排序，最初就能失去从小到大排序好的堆了，如下图所示，这就是咱们想要的后果：

3，残缺代码

import java.util.Arrays;

public class Head_Sort {public static void main(String[] args) {int[] arr={4,2,8,0,5,7,1,3,9};
        System.out.println("排序前:"+Arrays.toString(arr));
        System.out.println("排序后:"+Arrays.toString(HeapSort(arr)));
    }

    // 堆排序
    public static int[] HeapSort(int[] arr){
        int len=arr.length;
        /**
         * 第一步，初始化堆，最大堆，从小到大。目标是对元素排序
         * i 从齐全二叉树的第一个非叶子节点开始，也就是 len/2- 1 开始(数组下标从 0 开始)
         */
        for(int i=len/2-1;i>=0;i--){HeapAdjust(arr,i,len);
        }
        /**
         * 第二步，替换堆顶（最大）元素和二叉堆的最初一个叶子节点元素。目标是替换元素
         * i 从二叉堆的最初一个叶子节点元素开始，也就是 len- 1 开始(数组下标从 0 开始)
         */
        for(int i=len-1;i>=0;i--){int temp=arr[i];
            arr[i]=arr[0];
            arr[0]=temp;
            // 替换完之后须要从新调整二叉堆，从头开始调整，此时 Index=0
            HeapAdjust(arr,0,i);
        }
        return arr;
    }

    /**
     * 初始化堆
     * @param arr 待调整的二叉树(数组)
     * @param index 待调整的节点下标，二叉树的第一个非叶子节点
     * @param len 待调整的数组长度
     */
    public static void HeapAdjust(int[] arr,int index,int len){
        // 先保留以后节点的下标
        int max = index;
        // 保留左右孩子数组下标
        int lchild = index*2+1;
        int rchild = index*2+2;
        // 开始调整，左右孩子下标必须小于 len，也就是确保 index 必须是非叶子节点
        if(lchild<len && arr[lchild] > arr[max]){max=lchild;}
        if(rchild<len && arr[rchild] > arr[max]){max=rchild;}
        // 若产生了替换，则 max 必定不等于 index 了。此时 max 节点值须要与 index 节点值替换，下面替换索引值，这里替换节点值
        if(max!=index){int temp=arr[index];
            arr[index]=arr[max];
            arr[max]=temp;
            // 替换完之后须要再次对 max 进行调整，因为此时 max 有可能不满足最大堆
            HeapAdjust(arr,max,len);
        }
    }
}

运行后果：

4，算法剖析

4.1，工夫复杂度

建堆的时候初始化堆过程 (HeapAdjust) 是堆排序的要害，工夫复杂度为O(log n)，上面看堆排序的两个过程；

第一步，初始化堆，这一步工夫复杂度是O(n)；

第二步，替换堆顶元素过程，须要用到 n - 1 次循环，且每一次都要用到(HeapAdjust)，所以工夫复杂度为((n-1)*log n)~O(nlog n)；

最终工夫复杂度：O(n)+O(nlog n)，后者复杂度高于前者，所以 堆排序的工夫复杂度为 O(nlog n)；

4.2，空间复杂度

空间复杂度是O(1)，因为没有用到额定开拓的汇合空间。

4.3，算法稳定性

堆排序是不稳固的，比方说二叉树[6a，8，13，6b]，（这里的 6a 和 6b 数值上都是 6，只不过为了区别 6 所以这样）通过堆初始化后以及排序过后就变成[6b，6a，8，13]；可见堆排序是不稳固的。

退出移动版