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

• 基本介绍
  • 堆排序是利用堆这种数据结构设计而成的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度为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;// 将值调整到适合位置}
}