亚洲AV色欲色欲WWW,无码国产亚洲日韩国精品视频一区二区三区,亚洲第一二三四区

java 實(shí)現(xiàn)最小二叉堆排序

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

實(shí)現(xiàn)：

Java代碼:

/** 
 * @description 元素添加到末尾，和它的父節(jié)點(diǎn)比，如果比它小就交換 
 * @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;//當(dāng)前指向的數(shù)組元素位置  
        while(pointer!=0){  
            int leafPointer = pointer;//葉子節(jié)點(diǎn)位置  
            pointer = (pointer-1)/2;//根節(jié)點(diǎn)位置  
            root = minBinaryHeap[pointer];//根節(jié)點(diǎn)  
            if(num>=minBinaryHeap[pointer]){//永遠(yuǎn)把當(dāng)前數(shù)組元素看成葉子與其根比較或者換位  
                break;  
            }//如果根比葉子大 就交換位置  
            minBinaryHeap[pointer] = num;  
            minBinaryHeap[leafPointer] = root;  
              
        }  
    }  
    return minBinaryHeap;  
      
}  

Java代碼 :

/*** 
 * 用隨機(jī)數(shù)測(cè)試二叉堆排序 
 * 測(cè)試10遍，強(qiáng)迫癥似的變態(tài)... 
 */  
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 飛豬一號(hào) 閱讀(1488) 評(píng)論(0) 編輯收藏

新用戶注冊(cè) 刷新評(píng)論列表


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問(wèn) 管理

jialisoftw

java 實(shí)現(xiàn)最小二叉堆排序

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿

隨筆檔案

友情鏈接

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜