树结构的实际应用之堆排序

树结构的实际应用之堆排序

• 基本介绍
  • 堆排序是利用堆这种数据结构设计而成的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度为O(logn)，它也是不稳定排序。
  • 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。注意：没要求结点的左右孩子值的大小关系。
  • 每个结点的值都小于或者等于左右孩子结点的值，称为小顶堆。
  • 大顶堆举例说明
    
  • 一般升序采用大顶堆，降序采用小顶堆
• 堆排序基本思想
  • 将待排序序列构造成一个大顶堆
  • 此时，整个序列最大值就是根节点
  • 将其与末尾元素进行交换，将最大元素放到最后
  • 然后将剩余n-1个元素重新构造成一个堆，这样就会得到n个元素的次小值，如此反复执行，便能得到一个有序序列了。
• 堆排序步骤说明
  • 步骤一：构造初始堆，将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆）。原始的数组**[4,6,8,5,9]**
    • 假设无序序列的结构：
    • 此时，我们从最后一个非叶子结点开始，从右至左，从下到上调整。
      
    • 继续处理第二个非叶子结点
      
    • 这时，交换导致了子树[4,5,6]结构不符合，继续调整
      
    • 此时，我们就将一个无序序列构造成了一个大顶堆
  • 步骤二：将堆顶元素与末尾元素进行交换，使末尾元素最大，然后继续调整堆，再将堆顶元素与末尾元素交换得到第二大元素，如此反复进行交换、重建、交换。
• 堆排序代码实现

// 要求给一个数组[4,6,8,5,9]，要求使用堆排序算法，将数组升序排序
import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4,6,8,5,9};
        System.out.println("排序前");
        System.out.println(Arrays.toString(arr));

        System.out.println("排序后");
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 堆排序
     * @param arr
     */
    private static void heapSort(int[] arr) {
        int temp = 0;
        for(int i = arr.length / 2 - 1;i >= 0;i--) {
            adjustHeap(arr,i,arr.length);
        }

        // 将堆顶元素与末尾元素交换，将最大元素放到最后，重新调整结构，继续交换
        for(int j = arr.length - 1; j > 0;j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr,0,j);
        }
    }

    /**
     * 完成以i对应的非叶子结点的树调整成大顶堆
     */
    public static void adjustHeap(int[] arr,int i,int length) {
        int temp = arr[i];
        for(int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            // k中保存子节点中较大的值
            if(k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            // 交换结点
            if(arr[k] > temp) {
                // 调整位置
                arr[i] = arr[k];
                i = k; // 保存最后要存放的位置的下标
            }else {
                break; // 已找到，退出循环
            }
        }
        arr[i] = temp;// 将值调整到适合位置
    }
}