Go语言视频零基础入门到精通

javalearner

1. import java.util.*;
   
2. 
   
3. /**
   
4. *实现的小堆的插入和删除操作
   
5. * @author Arthur
   
6. */
   
7. public class Heap {
   
8. 
   
9.     /**
   
10.      * 递归实现
    
11.      * 删除一个堆中一个数据的时候，根据堆的性质，应该把相应的位置下移，才能保持住堆性质不变
    
12.      * @param heap 保持堆元素的数组
    
13.      * @param index 被删除的那个节点的位置
    
14.      */
    
15.     public static void heapDown(List< Integer> heap, int index) {
    
16.         //因为第一个位置存储的是空值，不在考虑之内
    
17.         int n = heap.size() - 2;
    
18. 
    
19.         //记录最小的那个儿子节点的位置
    
20.         int child = -1;
    
21. 
    
22.         //2*index>n说明该节点没有左右儿子节点了，那么就返回
    
23.         if (2 * index > n) {
    
24.             return;
    
25.         } //如果左右儿子都存在
    
26.         else if (2 * index < n) {
    
27. 
    
28.             //定义左儿子节点
    
29.             child = 2 * index;
    
30.             //如果左儿子大于右儿子的数值，取右儿子的下标
    
31.             if ((Integer) heap.get(child) > (Integer) heap.get(child + 1)) {
    
32.                 child++;
    
33.             }
    
34. 
    
35.         }//如果只有一个儿子（左儿子节点）
    
36.         else if (2 * index == n) {
    
37.             child = 2 * index;
    
38.         }
    
39. 
    
40.         if ((Integer) heap.get(child) < (Integer) heap.get(index)) {
    
41.             //交换堆中的child，和index位置的值
    
42.             swap(heap, child, index);
    
43. 
    
44.             //完成交换后递归调用，继续下降
    
45.             heapDown(heap, child);
    
46.         }
    
47.     }
    
48. 
    
49.     //非递归实现
    
50.     public static void heapDown2(List< Integer> heap, int index) {
    
51.         int child = 0;//存储左儿子的位置
    
52. 
    
53.         int temp = (Integer) heap.get(index);
    
54.         int n = heap.size() - 2;
    
55.         //如果有儿子的话
    
56.         for (; 2 * index <= n; index = child) {
    
57.             //获取左儿子的位置
    
58.             child = 2 * index;
    
59.             //如果只有左儿子
    
60.             if (child == n) {
    
61.                 child = 2 * index;
    
62.             } //如果右儿子比左儿子的数值小
    
63.             else if ((Integer) heap.get(child) > (Integer) heap.get(child + 1)) {
    
64.                 child++;
    
65.             }
    
66. 
    
67.             //如果数值最小的儿子比temp的值小
    
68.             if ((Integer) heap.get(child) < temp) {
    
69.                 //交换堆中的child，和index位置的值
    
70.                 swap(heap, child, index);
    
71.             } else {
    
72.                 break;
    
73.             }
    
74.         }
    
75.     }
    
76. 
    
77.     /**
    
78.      * 删除堆中最小的值，也就是删除位置是1的值，也就是根节点的值
    
79.      * 操作原理是：当删除根节点的数值时，原来的位置就会出现一个孔
    
80.      * 填充这个孔的方法就是，把最后的叶子的值赋给该孔，最后把该叶子删除
    
81.      * @param heap
    
82.      */
    
83.     public static void deleteMin(List< Integer> heap) {
    
84.         //把最后的一个叶子的数值赋值给1个位置
    
85.         heap.set(1, heap.get(heap.size() - 1));
    
86.         //下滤操作
    
87.         heapDown2(heap, 1);
    
88.        // heapDown(heap, 1);
    
89.         //把最后一个位置的数字删除
    
90.         heap.remove(heap.size() - 1);
    
91.     }
    
92. 
    
93.     public static void main(String args[]) {
    
94.         List< Integer> array = new ArrayList< Integer>(Arrays.asList(null, 1, 2, 5, 10, 3, 7,
    
95.                  11, 15, 17, 20, 9, 15, 8, 16));
    
96.         //deleteMin(array);结果是2 3 5 10 9 7 11 15 17 20 16 15 8  
    
97.         insert(array, 0);//结果是0 2 1 10 3 7 5 15 17 20 9 15 8 16 11
    
98.         print(array);
    
99.         System.out.println("-------------------------");
    
100.         List< Integer> array1=new ArrayList< Integer>();
     
101.         insert(array1,0);//无任何意义,占位.
     
102.         insert(array1, 1);insert(array1, 2);insert(array1, 5);insert(array1, 10);insert(array1, 3);insert(array1, 7);
     
103.         insert(array1, 11);insert(array1, 15);  insert(array1, 17);insert(array1, 20);insert(array1, 9);
     
104.         insert(array1, 15);insert(array1, 8);insert(array1, 16);
     
105.         print(array1);
     
106.     }
     
107. 
     
108.     //打印链表
     
109.     public static void print(List< Integer> list) {
     
110.         for (int i = 1; i < list.size(); i++) {
     
111.             System.out.print(list.get(i) + " ");
     
112.         }
     
113.         System.out.println();
     
114.     }
     
115. 
     
116.     //把堆中中的a,b位置的值互换
     
117.     public static void swap(List< Integer> heap, int a, int b) {
     
118.         //临时存储child位置的值
     
119.         int temp = (Integer) heap.get(a);
     
120. 
     
121.         //把index的值赋给child的位置
     
122.         heap.set(a, heap.get(b));
     
123. 
     
124.         //把原来的child位置的数值赋值给index位置
     
125.         heap.set(b, temp);
     
126.     }
     
127. 
     
128.     //向堆中插入元素
     
129.     public static void insert(List< Integer> heap, int value) {
     
130.         heap.add(value);
     
131.         //开始上升操作
     
132.         heapUp2(heap, heap.size() - 1);
     
133.        // heapUp(heap, heap.size() - 1);
     
134. 
     
135.     }
     
136. 
     
137.     //上升，让插入的数和父节点的数值比较，当大于父节点的时候就和节点的值相交换
     
138.     public static void heapUp(List< Integer> heap, int index) {
     
139. 
     
140.         //注意由于数值是从小标为一开始，当index = 1的时候，已经是根节点了
     
141.         if (index > 1) {
     
142.             //保存父亲的节点
     
143.             int parent = index / 2;
     
144. 
     
145.             //获取相应位置的数值
     
146.             int parentValue = (Integer) heap.get(parent);
     
147.             int indexValue = (Integer) heap.get(index);
     
148.             //如果父亲节点比index的数值大，就交换二者的数值
     
149.             if (parentValue > indexValue) {
     
150.                 //交换数值
     
151.                 swap(heap, parent, index);
     
152.                 //递归调用
     
153.                 heapUp(heap, parent);
     
154.             }
     
155. 
     
156.         }
     
157.     }
     
158. 
     
159.     //非递归实现
     
160.     public static void heapUp2(List< Integer> heap, int index) {
     
161.         int parent = 0;
     
162.         for (; index > 1; index /= 2) {
     
163.             //获取index的父节点的下标
     
164.             parent = index / 2;
     
165. 
     
166.             //获得父节点的值
     
167.             int parentValue = (Integer) heap.get(parent);
     
168.             //获得index位置的值
     
169.             int indexValue = (Integer) heap.get(index);
     
170.             
     
171.             //如果大于就交换
     
172.             if (parentValue > indexValue) {
     
173.                 swap(heap, parent, index);
     
174.             }
     
175.         }
     
176.     }
     
177. }
     

复制代码

运行结果:
D:java>java Heap
0 2 1 10 3 7 5 15 17 20 9 15 8 16 11 -------------------------
1 2 5 10 3 7 11 15 17 20 9 15 8 16
D:java>javac Heap.java D:java>java Heap
0 2 1 10 3 7 5 15 17 20 9 15 8 16 11
-------------------------
1 2 5 10 3 7 11 15 17 20 9 15 8 16

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/12/4/000804078.zip