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