寫在前面：
一覺醒來，我就突然有靈感了......
最小二叉堆定義：
二叉堆是完全二元樹或者是近似完全二元樹,最小二叉堆是父結點的鍵值總是小于或等于任何一個子節點的鍵值的堆堆。
存儲：
二叉堆一般用數組來表示。
根節點在數組中的位置是0，第n個位置的子節點分別在2n+1和 2n+2；
位置k的葉子的父節點位置為（k-1）/2；
實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
/** * @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; } |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
/*** * 用隨機數測試二叉堆排序 * 測試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(); } } |
如有疑問請留言或者到本站社區交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
原文鏈接：http://lynnlysh.iteye.com/blog/1767372
