1. 首頁 > 生活百科 > >

數據結構與算法【Java】08---樹結構的實際應用( 二 )

生活百科


文章插圖
1.3、堆排序代碼實現堆排序的理解還是比較困難的，尤其是代碼實現過程，下面提供兩種代碼實現，大家可以選擇適合自己的實現方法來理解堆排序

代碼實現（一）
import java.util.Arrays;public class HeapSort {public static void main(String[] args) {//升序--->大頂堆long startTime=System.currentTimeMillis();int arr[] = {5,3,7,1,4,6,2};heapSort(arr);long endTime=System.currentTimeMillis();System.out.println("程序運行時間： "+(endTime-startTime)+"ms");}//編寫一個堆排序的方法public static void heapSort(int arr[]) {int temp = 0;//完成我們最終代碼//將無序序列構建成一個堆，根據升序降序需求選擇大頂堆或小頂堆for(int i = arr.length / 2 -1; i >=0; i--) {adjustHeap(arr, i, arr.length);}/** 2).將堆頂元素與末尾元素交換，將最大元素"沉"到數組末端;3).重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，反復執行調整+交換步驟 ， 直到整個序列有序 。*/for(int j = arr.length-1;j >0; j--) {//交換temp = arr[j];arr[j] = arr[0];arr[0] = temp;adjustHeap(arr, 0, j);}System.out.println("數組=" + Arrays.toString(arr));}//將一個數組(二叉樹), 調整成一個大頂堆/*** 功能： 完成 將 以 i 對應的非葉子結點的樹調整成大頂堆* 舉例int arr[] = {4, 6, 8, 5, 9}; => i = 1 => adjustHeap => 得到 {4, 9, 8, 5, 6}* 如果我們再次調用adjustHeap 傳入的是 i = 0 => 得到 {4, 9, 8, 5, 6} => {9,6,8,5, 4}* @param arr 待調整的數組* @param i 表示非葉子結點在數組中索引* @param length 表示對多少個元素繼續調整，length 是在逐漸的減少*/public static void adjustHeap(int arr[], int i, int length) {int temp = arr[i];//先取出當前元素的值，保存在臨時變量//開始調整//說明//1. k = i * 2 + 1 k 是 i結點的左子結點for(int k = i * 2 + 1; k < length; k = k * 2 + 1) {if(k+1 < length && arr[k] < arr[k+1]) { //說明左子結點的值小于右子結點的值k++; // k 指向右子結點}if(arr[k] > temp) { //如果子結點大于父結點arr[i] = arr[k]; //把較大的值賦給當前結點i = k; //!!! i 指向 k,繼續循環比較} else {break;//!}}//當for 循環結束后，我們已經將以i 為父結點的樹的最大值，放在了 最頂(局部)arr[i] = temp;//將temp值放到調整后的位置}}結果：
【數據結構與算法【Java】08---樹結構的實際應用】
數據結構與算法【Java】08---樹結構的實際應用

文章插圖
代碼實現（二）
//交換數組中的元素public static void swap(int[]num ,int i,int j) {int temp=num[i];num[i]=num[j];num[j]=temp;}//將待排序的數組構建成大根堆public static void buildbigheap(int []num,int end) {//從最后一個非葉子節點開始構建,依照從下往上,從右往左的順序for(int i=end/2;i>=0;i--) {adjustnode(i, end, num);}}//調整該節點及其以下的所有節點public static voidadjustnode(int i,int end,int []num) {int left=2*i+1;int right=2*i+2;int big=i;//判斷小分支那個是大元素if(left<end&&num[i]<num[left])i=left;if(right<end&&num[i]<num[right])i=right;if(i!=big) {//交換順序之后需要繼續校驗swap(num, i, big);//重新校驗,防止出現交換之后根節點小于孩子節點的情況adjustnode(i, end, num);}}public static void main(String[] args) {int []num ={5,3,7,1,4,6,2};long startTime=System.currentTimeMillis();//第一次構建大根堆buildbigheap(num, num.length);for(int j=num.length-1;j>0;j--) {System.out.print("第"+(num.length-j)+"次排序前:");for(int k=0;k<num.length;k++) {System.out.print(num[k]+" ");}//交換隊頭已經排序得到的最大元素與隊尾元素swap(num, 0, j);System.out.print("第"+(num.length-j)+"次排序后:");for(int k=0;k<num.length;k++) {System.out.print(num[k]+" ");}System.out.println();//交換結束之后,大根堆已經被破壞,需要開始重新構建大根堆buildbigheap(num,j);}long endTime=System.currentTimeMillis();System.out.println("程序運行時間： "+(endTime-startTime)+"ms");}結果：
數據結構與算法【Java】08---樹結構的實際應用

文章插圖
2、赫夫曼樹2.1、簡介1、給定 n 個權值作為 n 個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度(wpl) 達到最小 ， 稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree), 還有的書翻譯為霍夫曼樹 。
2、赫夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近
重要概念和舉例說明