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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
public class MyPriorityQueue {
    Integer[] array;
    int size;   // 有效元素的个数

    public MyPriorityQueue(){
        array = new Integer[11];
        size = 0;
    }

    public MyPriorityQueue(int initCapacity){
        if(initCapacity < 1){
            throw new IllegalArgumentException("初始容量小于1");
        }

        array = new Integer[initCapacity];
        size = 0;
    }

    public MyPriorityQueue(Integer[] arr){
        // 1. 将arr中的元素拷贝到数组中
        array = new Integer[arr.length];
        for(int i = 0; i < arr.length; ++i){
            array[i] = arr[i];
        }
        size = arr.length;

        // 2. 找当前完全二叉树中倒数第一个叶子节点
        //    注意：倒数第一个叶子节点刚好是最后一个节点的双亲
        //    最后一个节点的编号size-1  倒数第一个非叶子节点的下标为(size-1-1)/2
        int lastLeafParent = (size-2)/2;

        // 3. 从倒数第一个叶子节点位置开始，一直到根节点的位置，使用向下调整
        for(int root = lastLeafParent; root >= 0; root--){
            shiftDown(root);
        }
    }

    boolean offer(Integer e){
        if(e == null){
            throw new NullPointerException("插入时候元素为null");
        }

        ensureCapacity();

        array[size++] = e;

        // 注意：当新元素插入之后，可能会破坏对的性质---需要向上调整
        shiftUp(size-1);
        return true;
    }

    // 将堆顶的元素删除掉
    public Integer poll(){
        if(isEmpty()){
            return null;
        }

        Integer ret = array[0];

        // 1. 将堆顶元素与堆中最后一个元素交换
        swap(0, size-1);

        // 2. 将堆中有效元素个数减少一个
        size--;  // size -= 1;

        // 3. 将堆顶元素往下调整到合适位置
        shiftDown(0);
        return ret;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public void clear(){
        size = 0;
    }

    // 功能：调整以parent为根的二叉树
    //    前提：必须要保证parent的左右子树已经满足堆的特性
    // 时间复杂度：O(logN)
    private void shiftDown(int parent){
        // 默认让child先标记左孩子---因为：parent可能有左没有右
        int child = parent*2 + 1;

        // while循环条件可以保证：parent的左孩子一定存在
        //       但是不能保证parent的右孩子是否存在
        while(child < size){
            // 1. 找到左右孩子中较小的孩子
            if(child+1 < size && array[child+1] < array[child]){
                child += 1;
            }

            // 2. 较小的孩子已经找到了
            //    检测双亲和孩子间是否满足堆的特性
            if(array[parent] > array[child]){
                swap(parent, child);

                // 大的双亲往下走了，可能会导致子树又不满足堆的特性
                // 因此需要继续往下调整
                parent = child;
                child = parent*2 + 1;
            }else{
                // 以parent为根的二叉树已经是堆了
                return;
            }
        }
    }

    private void shiftUp(int child){
        int parent = (child-1)/2;

        while(child != 0){
            if(array[child] < array[parent]){
                swap(child, parent);
                child = parent;
                parent = (child-1)/2;
            }else{
                return;
            }
        }
    }

    private void ensureCapacity(){
        if(array.length == size){
            int newCapacity = array.length*2;
            array = Arrays.copyOf(array, newCapacity);
        }
    }

    // 注意：left和right是数组的下标
    private void swap(int left, int right){
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

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
public static void swap(int[] array, int left, int right){
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    public static void shiftDown(int[] array, int size, int parent){
        int child = parent*2+1;

        while(child < size){
            // 找左右孩子中较大的孩子
            if(child+1 < size && array[child+1] > array[child]){
                child += 1;
            }

            // 双亲小于交大的孩子
            if(array[parent] < array[child]){
                swap(array, parent, child);
                parent = child;
                child = parent*2+1;
            }else{
                return;
            }
        }
    }

    // 假设：升序
    public static void heapSort(int[] array){
        // 1. 建堆----升序：大堆    降序：小堆---向下调整
        for(int root = (array.length-2)/2; root >= 0; root--){
            shiftDown(array, array.length, root);
        }


        // 2. 利用堆删除的思想来排序---向下调整
        int end = array.length-1;   // end标记最后一个元素
        while(end != 0){
            swap(array,0,end);
            shiftDown(array, end,0);
            end--;
        }
    }