本文共 3022 字，大约阅读时间需要 10 分钟。

二叉树——堆排序

基本介绍

1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序的算法，是不稳定排序，最好和最坏的时间复杂度都是O（nlogn）
2. 堆是具有以下性质的二叉树：每一个结点大于或等于其左右的子节点的值；或者每一个节点小于或者是等于其左右节点的值，必须是完全二叉树书。
3. 分类：
   • 大顶堆：每一个结点大于或者等于其左右节点的值，最大值在上面。用于升序排列
     * 顺序存储的表达式：arr[i] >= arr[2i + 1] &&arr[i] >= arr[2i+2]
   • 小顶堆：每一个结点小于或者是等于其左右节点的值，最小值在上面。用于降序排列。
     * 顺序存储的表达式：arr[i] <= arr[2i +1] &&arr[2i+2];
4. 图示：
   

排序思想

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

图解与步骤说明

对{4，6，8，5，9}进行排序

1. 将数组看作是对应的二叉树的顺序存储，然后对顺组进行整理，构建大顶堆
   • 在顺序存储结构中找到最后一个非叶子节点，代入公式arr.length/2-1,即为非叶子节点的对应坐标。
   • 从左至右从上至下进行调整，将最后一个非叶子结点对应的子树调整，将该树的最大的值放到对应子树的根节点位置。
   • 然后再对次一个非叶子节点进行调整，如此反复直至形成大顶堆
     *
2. 然后将大顶堆的根节点最大值沉到顺序存储结构的最后，然后不算最后一个结点，如此往复，直到所有的结点都经过排序，即为有序数列

实现代码

public static void heapSort(int[] arr) {
           System.out.println("堆排序");        int temp ;		for (int i = arr.length / 2  - 1;i >= 0;i --){
               adjustHeap(arr,i,arr.length);        }        //进行第一次排序，从左往右，从下到上        for (int i = arr.length - 1;i > 0;i --){
               temp = arr[i];            arr[i] = arr[0];            arr[0] = temp;            //将已经排序过的根结点的最大值，沉入到数组的最低端            adjustHeap(arr,0,i);            //然后在不算最后一个节点的情况下，对剩下的在进行有序化整理为大顶堆。            //没有必要从头进行整理，仅仅交换了顶点，所以只要从头开始        } } public static void adjustHeap(int arr[], int i, int length) {
           int temp = arr[i];        //设置交换值用于整理子树        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
           //从当前左子节点开始，每一次都是在下一层开始            if (k + 1< length && arr[k] < arr[k + 1]){
               //如果存在右子节点并且左子节点小于右子节点，那么就直接将k移动到右子节点。                k ++;                  }            if (arr[k] > temp){
                   arr[i] = arr[k];                i = k;                //如果k的值交换过，那就交换            }else{
               //如果没有交换，那就直接退出，因为下一层已经排好序了，所以可以以直接退出                break;            }        }        arr[i] = temp;        //将交换的值赋给原定的值    }

分析与总结：

1. 在如下这段代码中，for循环的迭代条件为什么每一次都是下个子节点？

for（int  k = i * 2 + 1;k < arr.length;k = 2 * k +1){
          if(k + 1 < length && arr[k] < arr[k + 1]){
                 k  ++;        }        if(arr[k] > temp){
                  temp = arr[k]        }else{
                  break         }        arr[i] = temp;}

• 答：首先第一次循环循环是从最后一个非叶子节点开始的，然后逐渐递减向左移动，直到最后一个节点形成对应的大顶堆，那么每一次改变仅仅改变根结点，而其他的已经修改过了。所以之后的每一次将根节点的值沉底之后就只需要比较某一个方向，不必担心某一方向存在比他更大的值了。因为对应子树的根结点就代表对应的最大值。

2. 在如下代码中，会不会出现叶子节点情况？

if（int i = arr.length / 2 - 1;i >= ;i --){
          adjustHeap(arr,i,arr.length)  }

• 答：堆排序仅仅针对完全二叉树，左连续在上，右连续在下，同时所有的叶子节点仅仅在最后两层。i是从最后一个非叶子节点开始算的，逐渐递减，所以一定会遍历所用的并且一定是非叶子节点。

3. 整体排序完成之后，后面每一次修改都是局部，所以仅仅比较两边，但是操作单边，较少操作步数。

代码常见问题

1. 第一次完整整理中，将小于等于误写成小于，取不到零，就取不到根节点，最后一个值不会参与排序，除了根节点，其余都只按照从大到小的顺序排列。

for (int i = arr.length / 2 - 1;i > 0;i --){
               adjustHeap(arr,i, arr.length);        }

2. 第一次全局整理过程中，没有加上for循环，仅仅对最后一个非叶子节点进行排序，没有对所有的进行排序

adjustHeap(arr,arr.length / 2 - 1, arr.length);

3. 再整理堆的代码中，没有让k进入改变的子树中，陷入死循环
   //开始比较该节点下一层的唯一的两个结点，根据各自的大小值，决定进入那一个分支

if (arr[k] > temp){
               arr[i] = arr[k];            k = i;        }else{
               break;        }

转载地址：http://xqgpb.baihongyu.com/