朱继鹏的博客

天道酬勤，全栈不停

0%

structure-heap

发表于 更新于 分类于
堆结构

堆的操作

  • 堆的构建
  • 堆的调整
    • 向上调整
    • 向下调整

堆的实现

堆排序

Heap.javaview raw
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
package dsa.structure.ds703_heap;

import java.util.Arrays;

public class Heap {
    public void heapSort1(int[] array) {
        genHeapByShiftUp(array);

        int len = array.length;
        while (len > 1) {
            swap(array, 0, --len);
            shiftDown(array, 0, len);
        }
    }

    public void heapSort2(int[] array) {
        genHeapByShiftDown(array);

        int len = array.length;
        while (len > 1) {
            swap(array, 0, --len);
            shiftDown(array, 0, len);
        }
    }

    private void genHeapByShiftUp(int[] arr) {
        // 从上往下处理时新结点是位于堆的底部，所以新结点需要的操作是向上调整
        // 因为不包含父结点的结点的不需要向上调整，所以第一个需要调整的结点是第一个包含父结点的结点
        // 所以第一个需要调整的结点的下标为i=1
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            shiftUp(arr, i);
        }
    }

    private void genHeapByShiftDown(int[] arr) {
        // 从下往上处理时新结点是位于堆的顶部，所以新结点需要的操作是向下调整
        // 因为不包含子结点的结点的不需要向下调整，所以最后一个需要调整的结点是最后一个包含子结点的结点
        // 所以最后一个需要调整的结点的下标为i=((len - 1) - 1)) / 2 = (len - 2) / 2
        int len = arr.length;
        for (int i = (len - 2) / 2; i >= 0; i--) {
            shiftDown(arr, i, len);
        }
    }

    public void shiftUp(int[] arr, int i) {
        int j = (i - 1) / 2;
        while (j >= 0) {
            if (arr[i] > arr[j]) {
                // 大顶堆，谁大谁在上
                swap(arr, i, j);

                i = j;
                j = (i - 1) / 2;
            } else {
                break;
            }
        }
    }

    public void shiftDown(int[] arr, int i, int heapSize) {
        int j = 2 * i + 1;
        while (j < heapSize) {
            // 大顶堆，选择左右结点中较大的那一个的下标
            j = j + 1 < heapSize && arr[j + 1] > arr[j] ? j + 1 : j;
            if (arr[j] > arr[i]) {
                // 大顶堆，谁大谁在上
                swap(arr, j, i);

                i = j;
                j = 2 * i + 1;
            } else {
                break;
            }
        }
    }

    private void swap(int[] array, int i, int j) {
        // 注释掉，因为每次判断带来的开销并不比无效的自我交换带来的开销少
        // if (i == j) {
        // return;
        // }

        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    public static void main(String[] args) {
        // HeapTest.testFixedExample(t -> new Heap().heapSort1(t));
        HeapTest.testRandomExample(t -> new Heap().heapSort1(t));

        // HeapTest.testFixedExample(t -> new Heap().heapSort2(t));
        HeapTest.testRandomExample(t -> new Heap().heapSort2(t));
    }

    public static class HeapTest {
        public static interface HeapFunc {
            void apply(int[] array);
        }

        private static void testHeap(int[] array, HeapFunc f) {
            int[] mybak = Arrays.copyOf(array, array.length);
            Arrays.sort(mybak);

            f.apply(array);

            int[] result = array;
            int[] expect = mybak;

            TestUtils.check("堆", result, expect);
        }

        private static void testRandomExample(HeapFunc f) {
            for (int i = 0; i < 36; i++) {
                testHeap(random(9), f);
                testHeap(random(10), f);
            }
        }

        private static void testFixedExample(HeapFunc f) {
            int[] array = new int[] { 310, 78, 237, 773, 96, 165, 70, 757, 665, 508 };

            testHeap(array, f);
        }

        public static int[] random(int n) {
            int[] array = new int[n];
            for (int i = 0; i < array.length; i++) {
                array[i] = (int) (Math.random() * 1000) + 1;
            }

            return array;
        }
    }

    public static class TestUtils {

        public static boolean check(String name, Object result, Object expect) {
            boolean ok = java.util.Objects.deepEquals(result, expect);
            printCheck(name, toString(result), toString(expect), ok);
            return ok;
        }

        private static String toString(Object o) {
            if (o instanceof Object[]) {
                return java.util.Arrays.deepToString((Object[]) o);
            } else if (o instanceof int[]) {
                return java.util.Arrays.toString((int[]) o);
            } else if (o instanceof double[]) {
                return java.util.Arrays.toString((double[]) o);
            } else if (o instanceof char[]) {
                return java.util.Arrays.toString((char[]) o);
            } else {
                return java.util.Objects.toString(o);
            }
        }

        public static void printCheck(String name, String result, String expect, boolean ok) {
            System.out.println();
            System.out.println("--->");

            System.out.println("result: " + result);
            System.out.println("expect: " + expect);

            System.out.println();
            if (ok) {
                System.out.println("比较结果为: 正确(right)");
            } else {
                System.out.println("比较结果为: 错误(error)");
            }

            System.out.println("<---");
            System.out.println();

            if (!ok) {
                throw new RuntimeException(String.format("ERROR: [%s]的测试失败", name));
            }
        }
    }
}

优先级队列

PriorityQueue.javaview raw
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
package dsa.structure.ds703_heap;

import java.util.Arrays;

public class PriorityQueue {
    private int size = 0;
    private int[] array = null;

    public PriorityQueue(int capacity) {
        array = new int[capacity];
    }

    public boolean enqueue(int v) {
        int i;
        if (size == array.length) {
            i = indexOfObsolete(array, v);
            if (i < 0) {
                return true;
            }
        } else {
            i = size;
            size++;
        }

        array[i] = v;

        // 如果不存在淘汰，新的值v是直接添加到堆的底部，需要向上调整
        // 如果存在淘汰，由于是小顶堆，所以需要淘汰的最大值位于堆的底部
        // 由于新的值v会替换淘汰的最大值的位置，所以新的值v是位于堆的底部，需要向上调整
        shiftUp(array, i);

        return true;
    }

    public Integer dequeue() {
        if (size == 0) {
            return null;
        }

        int v = array[0];

        // swap(array, 0, --size);
        array[0] = array[--size];
        shiftDown(array, 0, size);

        return v;
    }

    public int size() {
        return size;
    }

    public void fillin(int[] array) {
        for (int v : array) {
            enqueue(v);
        }
    }

    public int[] collect() {
        // 不能直接使用size，因为size在出队的时候会改变
        int c = size;

        int[] a = new int[c];
        for (int i = 0; i < c; i++) {
            a[i] = dequeue();
        }

        return a;
    }

    public int[] toArray() {
        // // just for test
        // int[] a = Arrays.copyOf(array, array.length);
        // Arrays.sort(a);
        // return a;

        int[] bakArray = Arrays.copyOf(array, array.length);
        int bakSize = size;

        int[] ret = collect();

        array = bakArray;
        size = bakSize;

        return ret;
    }

    private int indexOfObsolete(int[] arr, int v) {
        int p = -1;

        // 小顶堆，淘汰最大的
        int max = v;
        
        // 由于最大的值没有子结点，所以查找的起始位置为第一个叶子结点
        // 因为最后一个非叶子结点的下标为 ((size - 1) - 1) / 2 = (size - 2) / 2
        // 所以第一个叶子结点的下标为 (size - 2) / 2 + 1
        for (int i = (size - 2) / 2 + 1; i < size; i++) {
            if (arr[i] > max) {
                max = arr[i];

                p = i;
            }
        }

        return p;
    }

    public void shiftUp(int[] arr, int i) {
        int j = (i - 1) / 2;
        while (j >= 0) {
            if (arr[i] < arr[j]) {
                // 小顶堆，谁小谁在上
                swap(arr, i, j);

                i = j;
                j = (i - 1) / 2;
            } else {
                break;
            }
        }
    }

    public void shiftDown(int[] arr, int i, int heapSize) {
        int j = 2 * i + 1;
        while (j < heapSize) {
            // 小顶堆，选择左右结点中较小的那一个的下标
            j = j + 1 < heapSize && arr[j + 1] < arr[j] ? j + 1 : j;
            if (arr[j] < arr[i]) {
                // 小顶堆，谁小谁在上
                swap(arr, j, i);

                i = j;
                j = 2 * i + 1;
            } else {
                break;
            }
        }
    }

    private void swap(int[] array, int i, int j) {
        // 注释掉，因为每次判断带来的开销并不比无效的自我交换带来的开销少
        // if (i == j) {
        // return;
        // }

        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    public static void main(String[] args) {
        // PriorityQueueTest.testFixedExample(t -> testPriorityQueue(t));
        PriorityQueueTest.testRandomExample(t -> testPriorityQueue(t));
    }

    private static int[] testPriorityQueue(int[] array) {
        // int capacity = array.length * 2;
        int capacity = array.length / 2;
        PriorityQueue queue = new PriorityQueue(capacity);

        queue.fillin(array);

        return queue.toArray();
    }

    public static class PriorityQueueTest {
        public static interface PriorityQueueFunc {
            int[] apply(int[] array);
        }

        private static void testPriorityQueue(int[] array, PriorityQueueFunc f) {
            int[] mybak = Arrays.copyOf(array, array.length);
            Arrays.sort(mybak);

            int[] result = f.apply(array);
            int[] expect = Arrays.copyOf(mybak, result.length);

            TestUtils.check("优先级队列", result, expect);
        }

        private static void testRandomExample(PriorityQueueFunc f) {
            for (int i = 0; i < 36; i++) {
                testPriorityQueue(random(19), f);
                testPriorityQueue(random(20), f);
            }
        }

        private static void testFixedExample(PriorityQueueFunc f) {
            int[] array = new int[] { 310, 78, 237, 773, 96, 165, 70, 757, 665, 508 };

            testPriorityQueue(array, f);
        }

        public static int[] random(int n) {
            int[] array = new int[n];
            for (int i = 0; i < array.length; i++) {
                array[i] = (int) (Math.random() * 1000) + 1;
            }

            return array;
        }
    }

    public static class TestUtils {

        public static boolean check(String name, Object result, Object expect) {
            boolean ok = java.util.Objects.deepEquals(result, expect);
            printCheck(name, toString(result), toString(expect), ok);
            return ok;
        }

        private static String toString(Object o) {
            if (o instanceof Object[]) {
                return java.util.Arrays.deepToString((Object[]) o);
            } else if (o instanceof int[]) {
                return java.util.Arrays.toString((int[]) o);
            } else if (o instanceof double[]) {
                return java.util.Arrays.toString((double[]) o);
            } else if (o instanceof char[]) {
                return java.util.Arrays.toString((char[]) o);
            } else {
                return java.util.Objects.toString(o);
            }
        }

        public static void printCheck(String name, String result, String expect, boolean ok) {
            System.out.println();
            System.out.println("--->");

            System.out.println("result: " + result);
            System.out.println("expect: " + expect);

            System.out.println();
            if (ok) {
                System.out.println("比较结果为: 正确(right)");
            } else {
                System.out.println("比较结果为: 错误(error)");
            }

            System.out.println("<---");
            System.out.println();

            if (!ok) {
                throw new RuntimeException(String.format("ERROR: [%s]的测试失败", name));
            }
        }
    }
}
只想买包辣条