樹結構的實際應用之堆排序

• 基本介紹
  • 堆排序是利用堆這種數據結構設計而成的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度為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;// 將值調整到適合位置}
}