大根堆的创建（视频讲解）

注意：

1. 其实左右节点 都是要去找父亲节点，不如遍历的时候，就通过父亲节点遍历（可以减少遍历次数以及 遍历经过中的循环次数）

for (int parent = (usedSize-1-1) / 2; parent >= 0 ; parent--)

public class TestHeap {

    public int[] elem;
    public int usedSize;//当前堆当中的有效的元素的数据个数

    public TestHeap() {
        this.elem = new int[10];
        this.usedSize = 0;
    }

    public void initArray(int[] array) {
        elem = Arrays.copyOf(array,array.length);
        usedSize = elem.length;
    }

    /**
     * 建堆:【大根堆】
     * 时间复杂度：O(n)
     */

    public void createHeap() {
        for (int parent = (usedSize-1-1) / 2; parent >= 0 ; parent--) {
            shiftDown(parent,usedSize);
        }
    }

    /**
     * 实现 向下调整
     * @param parent 每棵子树的根节点的下标
     * @param len 每棵子树的结束位置
     */

    private void shiftDown(int parent ,int len) {
        int child = 2 * parent + 1;
        //最起码是有左孩子
        while (child < len) {
            //判断 左孩子 和 右孩子  谁最大,前提是  必须有  右孩子
            if(child+1 < len && elem[child] < elem[child+1]) {
                child++;//此时 保存了最大值的下标
            }
            if(elem[child] > elem[parent]) {
                swap(elem,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    private void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56