您好,登錄后才能下訂單哦!
這篇文章給大家介紹最小二叉樹堆排序怎么利用java 實現(xiàn),內容非常詳細,感興趣的小伙伴們可以參考借鑒,希望對大家能有所幫助。
最小二叉堆定義:
二叉堆是完全二元樹或者是近似完全二元樹,最小二叉堆是父結點的鍵值總是小于或等于任何一個子節(jié)點的鍵值的堆堆。
存儲:
二叉堆一般用數(shù)組來表示。
根節(jié)點在數(shù)組中的位置是0,第n個位置的子節(jié)點分別在2n+1和 2n+2;
位置k的葉子的父節(jié)點位置為(k-1)/2;
實現(xiàn):
/** * @description 元素添加到末尾,和它的父節(jié)點比,如果比它小就交換 * @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;//當前指向的數(shù)組元素位置 while(pointer!=0){ int leafPointer = pointer;//葉子節(jié)點位置 pointer = (pointer-1)/2;//根節(jié)點位置 root = minBinaryHeap[pointer];//根節(jié)點 if(num>=minBinaryHeap[pointer]){//永遠把當前數(shù)組元素看成葉子與其根比較或者換位 break; }//如果根比葉子大 就交換位置 minBinaryHeap[pointer] = num; minBinaryHeap[leafPointer] = root; } } return minBinaryHeap; }
/*** * 用隨機數(shù)測試二叉堆排序 * 測試10遍,強迫癥似的變態(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(); } }
關于最小二叉樹堆排序怎么利用java 實現(xiàn)就分享到這里了,希望以上內容可以對大家有一定的幫助,可以學到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到。
免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內容。