日韩欧美的一区二区,久久久久久有精品国产,黄色精品一二区

java 實現最小二叉堆排序

寫在前面：
一覺醒來，我就突然有靈感了......
最小二叉堆定義：
二叉堆是完全二元樹或者是近似完全二元樹,最小二叉堆是父結點的鍵值總是小于或等于任何一個子節點的鍵值的堆堆。
存儲：
二叉堆一般用數組來表示。
根節點在數組中的位置是0，第n個位置的子節點分別在2n+1和 2n+2；
位置k的葉子的父節點位置為（k-1）/2；

實現：

Java代碼:

/** 
 * @description 元素添加到末尾，和它的父節點比，如果比它小就交換 
 * @param array 
 *  
 * @author LynnWong 
 */  
private int[] getMinBinaryHeap(int[] array){  
    int N = array.length;  
    int minBinaryHeap[] = new int[N];  
    int root;//根的值  
    int heapSize = 0;//記錄插入位置  
    for(int num : array){  
        minBinaryHeap[heapSize]=num;  
        ++heapSize;  
        int pointer = heapSize-1;//當前指向的數組元素位置  
        while(pointer!=0){  
            int leafPointer = pointer;//葉子節點位置  
            pointer = (pointer-1)/2;//根節點位置  
            root = minBinaryHeap[pointer];//根節點  
            if(num>=minBinaryHeap[pointer]){//永遠把當前數組元素看成葉子與其根比較或者換位  
                break;  
            }//如果根比葉子大 就交換位置  
            minBinaryHeap[pointer] = num;  
            minBinaryHeap[leafPointer] = root;  
              
        }  
    }  
    return minBinaryHeap;  
      
}  

Java代碼 :

/*** 
 * 用隨機數測試二叉堆排序 
 * 測試10遍，強迫癥似的變態... 
 */  
public void text(){  
    for(int i=0;i<10;i++){  
        Random rnd = new Random();   
        int [] lala = {rnd.nextInt(6),rnd.nextInt(6),rnd.nextInt(6),rnd.nextInt(6),rnd.nextInt(6),rnd.nextInt(6)};  
        System.out.print("輸入：");  
        for(int a : lala){  
            System.out.print(a+" ");  
        }  
        System.out.println();  
        int []array = this.getMinBinaryHeap(lala);  
        System.out.print("輸出：");  
        for(int a : array){  
            System.out.print(a+" ");  
        }  
        System.out.println();  
    }  
} 

posted on 2013-01-10 14:01 飛豬一號閱讀(1490) 評論(0) 編輯收藏

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理

jialisoftw

java 實現最小二叉堆排序

導航

統計

常用鏈接

留言簿

隨筆檔案

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜