数据结构之二叉堆(构建堆，堆排序)

1. public class Heap  
2.     {  
3.   
4.         public static void main(String[] args)  
5.             {  
6.                 // TODO Auto-generated method stub  
7.                 //System.out.println((int)-1.5);  
8.                 int []array={4,2,7,9,3,6,1,12,10,5};  
9.                 System.out.println("原始：");  
10.                 printHeapByLevel(array);  
11.                 System.out.println("最小堆：");  
12.                 getMinHeap(array);  
13.                 printHeapByLevel(array);  
14.                 //System.out.println(Math.log(i+1)/Math.log(2));  
15.                   
16.                sort(array);  
17.                printHeapByLevel(array);  
18.             }  
19.         /* 
20.          * 堆的性质（最小堆为例）： 
21.          *    0.根节点为最小值 
22.          *    1.堆可以看做是一个完全二叉树（即孩子节点从左向右排列） 
23.          *    2.堆的高度lgn/lg2(n为节点的数目) 
24.          *    3.第i节点的左孩子节点是2*i+1,右孩子节点为2*i+2 
25.          *    4.以任意一个节点作为根节点，那么该节点都是堆 
26.          *    5.可以用一个数据来表示堆 
27.          */  
28.         /* 
29.          * 构建堆的原理： 
30.          *   上滤 
31.          *   在最后一个节点后建立一个空节点，新插入的节点和父节点比较： 
32.          *      1，比父节点大，那么直接插入在这个空堆处 
33.          *      2，比父节点小，那么该父节点下移至该空节点 
34.          *      3，重复1,2直至插入堆中 
35.          */  
36.         public static void getMinHeap(int []array)  
37.         {  
38.             for(int i=1;i<array.length;i++)  
39.                 insert(array, i);  
40.         }  
41.         //从插入第k个位置的值到堆中，插入一个的最坏情况就是lgN  
42.         public static void insert(int []arrary,int k)  
43.         {  
44.             int insert=arrary[k];  
45.             while(k>0)//一直和父节点比较  
46.                 {  
47.                     if(insert<arrary[(k-1)/2])//需要插入的元素小于该父节点，那么父节点下移  
48.                         {  
49.                            arrary[k]=arrary[(k-1)/2];  
50.                            k=(k-1)/2;  
51.                            if(k==0)  
52.                                arrary[k]=insert;  
53.                         }  
54.                     else //需要插入的元素大于该父节点，该节点正好可以插在最后一个位置  
55.                         {  
56.                             arrary[k]=insert;  
57.                             break;  
58.                         }  
59.                 }  
60.         }  
61.         //按层次打印一个堆  
62.         public static void printHeapByLevel(int []array)  
63.         {  
64.             int height=0;  
65.             for(int i=0;i<array.length;i++)  
66.                 {  
67.                     int tempHeight=(int)(Math.log(i+1)/Math.log(2));  
68.                     if(tempHeight>height)  
69.                         {  
70.                            System.out.println();  
71.                            System.out.print(array[i]+" ");  
72.                            height=tempHeight;  
73.                         }  
74.                     else   
75.                         System.out.print(array[i]+" ");  
76.                 }  
77.             System.out.println();  
78.         }  
79.         /* 
80.          * 二叉树的排序 
81.          */  
82.         public static void sort(int []array)  
83.         {  
84.             for(int i=0;i<array.length;i++)  
85.                 {  
86.                     deleteMin(array, array.length-1-i);  
87.                 }  
88.         }  
89.         /* 
90.          * 删除一个根节点，也就是最小值 
91.          * 那么子节点要上浮 
92.          * 可以根据此用堆排序 
93.          * 将删除的最小值放在数组的最后一个位置，节省空间 
94.          * 根节点为i（0,1,2,3...） 
95.          * 左孩子节点为：2*i+1 
96.          * 右孩子节点为：2*i+2 
97.          * n是剩下的节点 
98.          */  
99.         public static void deleteMin(int []array,int n)  
100.         {  
101.             int min=array[0];  
102.             int temp=0;//寻找一个孩子填充根节点  
103.             while(2*temp+1<n)//无子节点  
104.                 {  
105.                     if(array[2*temp+1]>array[2*temp+2])  
106.                         {  
107.                           array[temp]=array[2*temp+2];  
108.                           temp=2*temp+2;  
109.                         }  
110.                     else   
111.                         {  
112.                           array[temp]=array[2*temp+1];  
113.                           temp=2*temp+1;  
114.                         }  
115.                 }  
116.             //此刻temp为要空，要将最后一个节点值放在temp这个位置上，并且移动temp  
117.             array[temp]=array[n];  
118.             array[n]=min;  
119.             if(temp<n)//要调整的节点后面还有节点  
120.                 insert(array, temp);  
121.         }  
122.     }