最大堆构建和堆排序

1 输入一个任意长度的无规律数组，把该数组构建为最大堆

2 用构建好的最大堆，进行堆排序

 1 public class Solution {
 2     
 3     /**
 4      * 构建堆
 5      * @param array
 6      */
 7     public static void buildMaxHeap(int[] array) {
 8         
 9     /*    for (int i = array.length / 2; i >= 0; i--) {
10             adjust(array, i, array.length);    
11         }*/
12         /** 以树的最后一个节点的父节点为根开始调整  */
13         int last = array.length - 1;
14         int pos = (last - 1) / 2;
15         while (pos >= 0) {
16             adjust(array, pos--, array.length);
17         }
18     }
19     
20     
21     /**
22      * 把以root为根的那棵子树调整为最大堆, 此时以root为根的左右子树都以调整为最大堆
23      * @param array
24      * @param root
25      * @param len
26      */
27     public static void adjust(int[] array, int root, int len) {
28         int l = root * 2 + 1;
29         int r = root * 2 + 2;
30         int largest = root;
31         
32         /** 特别要考虑满二叉树的情况 */
33         //parent节点有左孩子
34         if (l < len && array[l] > array[largest]) {
35                 largest = l;
36         }
37         //parent节点有右孩子
38         if (r < len && array[r] > array[largest]) {
39                 largest = r;
40         }
41         
42         //如果以root为根的堆
43         if (largest != root) {
44             swap(array, root, largest);
45             adjust(array, largest, len);
46         }
47     }
48     
49     
50     /**
51      *  堆排序函数
52      * @param array
53      * @param len
54      */
55     public static void heapSort(int[] array) {
56         
57         int len = array.length;
58         
59         while (len > 1) {
60             /** 堆顶的元素为数组中所有元素的最大值
61                                 出堆顶，把堆对应树的最后那个节点放到堆顶（从堆顶向下调整）
62                                 此时，堆对应树的最后那个节点位置为空，把刚出的堆顶最大值放入该空位 */
63             swap(array, 0, len - 1); //拿堆对应的树的最后一个节点与根节点交换
64             len--;
65             adjust(array, 0, len);
66         }
67     }
68     
69     public static void print(int[] array) {
70         for (int i = 0; i < array.length;  i++) {
71             System.out.println(i + ", " + array[i]);
72         }
73     }
74     
75     public static void swap(int[] array, int t1, int t2) {
76         int temp = array[t1];
77         array[t1] = array[t2];
78         array[t2] = temp;
79     }
80     
81     
82     
83     public static void main(String[] args) {
84         
85         //生成随机数数组
86         int[] array = { 53, 17, 78, 9, 45, 65, 87};
87         
88         buildMaxHeap(array);
89         System.out.println("建堆完成：");
90         print(array);
91         System.out.println("------------------");
92         
93         heapSort(array);
94         print(array);
95     }
96 }

上述方案调整堆的原理为：

1）叶子节点，无子树，可以把叶结点看作为一棵树，为最大堆

2）从最后一个叶节点开始

3）让pos指向该叶结点的父节点，pos指向一个子树，其孩子（为叶结点）已是最大堆，然后我们只要把这棵树调整为最大堆

4）pos减1，走3），直到pos指向数组索引0处，把堆顶调整完成