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             else34                 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             else41                 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 }