最小堆的基础操作(Java)

1 public class test
 2 {
 3     public static void main(String[] args)
 4     {
 5         int[] array = new int[] {3,5,6,11,20,8,9,2,7};
 6         createMinimumHeap(array);
 7         for(int value : array)
 8             System.out.print(value + " ");
 9         System.out.println();
10         for(int i = 0; i < array.length; i++)
11             System.out.print(extract_Min(array, array.length - i) + " ");
12     }
13     
14     //1 建堆
15     public static void createMinimumHeap(int[] array)
16     {
17         int k = array.length / 2 - 1;
18         while(k >= 0)
19         {
20             Min_Heapify(array, k, array.length);
21             k -= 1;
22         }
23     }
24 
25     //2 最小堆化
26     public static void Min_Heapify(int[] array, int k, int size)
27     {
28         int min_index;
29         while(k <= size / 2 - 1)
30         {
31             if(k * 2 + 2 >= size)
32                 min_index = k * 2 + 1;
33             else
34                 min_index = array[k * 2 + 1] < array[k * 2 + 2] ? k * 2 + 1 : k * 2 + 2;
35             if(array[k] > array[min_index])
36             {
37                 swap(array, k, min_index);
38                 k = min_index;
39             }
40             else
41                 break;
42         }
43     }
44 
45     //3 提取最小元素
46     public static int extract_Min(int[] array, int size)
47     {
48         int key = array[0];
49         array[0] = array[size - 1];
50         //最小堆化
51         Min_Heapify(array, 0, size - 1);
52         return key;
53     }
54     
55     //4 插入元素
56     //将插入的元素放在数组最后 依次与其父亲结点进行比较 直到根结点
57     
58     public static void swap(int[] a, int i, int j)
59     {
60         int tmp = a[i];
61         a[i] = a[j];
62         a[j] = tmp;
63     }
64 }      

转载于:https://www.cnblogs.com/Huayra/p/10874932.html