树、二叉树的简单介绍

可以用数组表示一颗二叉树（数组下标从0开始）

• 左子节点下标是 2n+1 (n是父节点下标)
• 右子节点下标是 2n+2 (n是父节点下标)
• 父节点下标是 n/2-1 （n是左子节点或者右子节点下标）

堆的概念

• 二叉堆是完全二叉树或者是近似完全二叉树
• 二叉堆满足两个特性：
  • 父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值
  • 每个节点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）
• 任意节点的值都大于其子节点的值————大顶堆，堆的最大值在根节点。

• 任意节点的值都小于其子节点的值————小顶堆，堆的最小值在根节点。

堆排序

步骤

• 第一步：堆化

  • 反向调整使得每个子树都是大顶堆或者小顶堆

  • 从n/2-1个元素开始向下修复，将每个节点修复为大（小）顶堆，修复完成后，数组具有大（小）顶堆的性质

    举个例子：
    初始给定数组为[2,7,26,25,19,17]
    它所形成的二叉堆是
    

    堆化以后变成大顶堆
    

    数组变为[26,25,17,7,19,2]

• 第二步：调整

  • 不停地把堆顶和未处理数组的最后一个元素交换，把堆顶也就是较大元素放到数组末端，每交换一次都要进行调整，维持二叉堆结构。

代码实现

法一：采用递归方式进行调整操作

    public static void main(String[] args) {
        int[] arr = {2,5,6,21,6,4,2,6,2};
        heapSort(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }
    private static void heapSort(int[] arr){
        mikeMaxHeap(arr);                   //1.先进行堆化
        for(int x = arr.length-1;x>=0;x--){ //2.再进行调整
            swap(arr,0,x);  //把堆顶(0号元素)和最后一个元素对调
            maxHeapFixDown(arr,0,x);  //缩小堆的范围，对堆顶元素进行向下调整
        }
    }
    private static void mikeMaxHeap(int[] arr) {
        int n = arr.length - 1;
        for (int i = (n - 1) / 2; i >= 0; i--) { //从「第一个非叶子节点」开始向前调整，叶子节点没必要调整
            maxHeapFixDown(arr, i, n);
        }
    }

    private static void maxHeapFixDown(int[] arr, int i, int n) {
        // 1.找到左右孩子
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // 2.让max指向了左右孩子中较大的那个
        if (left >= n)     //左孩子已经越界，i就是叶子节点
            return;
        int max = left; //先默认左右孩子中较大的那个是左孩子，简化代码
        if (right >= n)    //右孩子越界，孩子中较大的就是左孩子
            max = left;
        else {          //左右孩子都没越界，max指向较大的那个
            if (arr[right] > arr[left])
                max = right;
        }
        // 3.交换孩子节点和父亲节点
        if(arr[i]>=arr[max])  // 如果arr[i]比两个孩子都要大，不用调整
            return;

        swap(arr,i,max);   //否则，找到两个孩子中较大的，和i交换

        // 4.大孩子那个位置的值发生了变化，i变更为大孩子那个位置，递归调整
        maxHeapFixDown(arr, max, n);
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

法二：采用循环方式进行调整操作

只需要修改maxHeapFixDown方法

    public static void main(String[] args) {
        int[] arr = {2,5,6,21,6,4,2,6,2};
        heapSort(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }
    private static void heapSort(int[] arr) {
        mikeMaxHeap(arr);       //1.先进行堆化
        for (int x = arr.length - 1; x >= 0; x--) { //2.再进行调整
            swap(arr, 0, x);  //把堆顶(0号元素)和最后一个元素对调
            maxHeapFixDown(arr, 0, x);  //缩小堆的范围，对堆顶元素进行向下调整
        }
    }

    private static void mikeMaxHeap(int[] arr) {
        int n = arr.length - 1;
        //从「第一个非叶子节点」开始向前调整，叶子节点没必要调整
        for (int i = (n - 1) / 2; i >= 0; i--) {
            maxHeapFixDown(arr, i, n);
        }
    }

    private static void maxHeapFixDown(int[] arr, int index, int size) {
        int left = index * 2 + 1;
        while (left < size) {
            //如果存在右节点，则largest等于左右节点中较大者的下标
            //如果不存在右节点，则largest等于左节点的下标
            //一条语句同时满足两个条件，选出子节点中的较大者给largest
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
            //选出子节点和父节点中的较大者
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);  //交换
            index = largest;        //进入下一次循环（下沉），重新计算index和left
            left = index * 2 + 1;
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

时间复杂度分析

第一步：建立大根堆的过程。

只从数组第2n-1(n 是数组长度)个元素开始倒着往前处理。
最后一层节点数大约n/2，因为是叶子节点，所以对其操作就只是看了一眼，操作数为1。
倒数第二层节点数大约n/4，操作是看一眼加上一次交换，操作数为2。
同理，倒数第三层节点数为n/8，操作数为3。
写出总的复杂度公式：

\(\mathrm{T}\left( \mathrm{n} \right) =\frac{\mathrm{n}}{2}\times 1+\frac{\mathrm{n}}{4}\times 2+\frac{\mathrm{n}}{8}\times 3+\mathrm{……}\)

利用错为相减法可以求出通项公式

\[\mathrm{T}\left( \mathrm{n} \right) =\frac{\mathrm{n}}{2}\times 1+\frac{\mathrm{n}}{4}\times 2+\frac{\mathrm{n}}{8}\times 3+\frac{\mathrm{n}}{16}\times 4+\mathrm{……} \\ 2\mathrm{T}\left( \mathrm{n} \right) =\frac{\mathrm{n}}{2}\times 2+\frac{\mathrm{n}}{2}\times 2+\frac{\mathrm{n}}{4}\times 3+\frac{\mathrm{n}}{8}\times 4+\mathrm{……} \\ \mathrm{T}\left( \mathrm{n} \right) =\mathrm{n}+\frac{\mathrm{n}}{2}+\frac{\mathrm{n}}{4}+\frac{\mathrm{n}}{8}+\mathrm{……} \\ \approx \mathrm{O}\left( \mathrm{n} \right) \]

所以把数组变成大根堆的时间复杂度是O(n)

第二步：调整的过程需要交换 n 次，每交换一次都需要进行调整，每次调整复杂度是logn级别，总的复杂度是O(nlogn)

所以堆排序的总时间复杂度是O(nlogn)

空间复杂度分析

没用申请额外空间，空间复杂度是 O(1)