数据结构之优先队列

 1 package com.queue;
 2 
 3 /**
 4  *
 5  */
 6 public interface Queue<E> {
 7 
 8     /**
 9      * 向队列中添加一个元素，入队。对应栈的入栈。
10      *
11      * @param e
12      */
13     public void enqueue(E e);
14 
15     /**
16      * 从队列中取出一个元素，出队。对应栈的出栈。
17      *
18      * @return
19      */
20     public E dequeue();
21 
22     /**
23      * 获取到队列中队首的元素。对应栈的查看栈顶的元素。
24      *
25      * @return
26      */
27     public E getFront();
28 
29     /**
30      * 获取到队列的大小
31      *
32      * @return
33      */
34     public int getSize();
35 
36     /**
37      * 判断队列是否为空
38      *
39      * @return
40      */
41     public boolean isEmpty();
42 
43 }

  1 package com.maxHeap;
  2 
  3 import com.company.Array;
  4 
  5 import java.util.Random;
  6 
  7 /**
  8  * 最大堆，由于规定了每个节点的值都要大于等于左右孩子节点的值，所以要具有可比较性
  9  */
 10 public class MaxHeap<E extends Comparable<E>> {
 11 
 12     // 动态数组
 13     public Array<E> data;
 14 
 15     // ctrl + f12查看方法，变量等等
 16     // fn + alt + insert 构造方法
 17 
 18     /**
 19      * 如果直到动态数组的大小，可以直接创建
 20      *
 21      * @param capacity
 22      */
 23     public MaxHeap(int capacity) {
 24         data = new Array<>(capacity);
 25     }
 26 
 27 
 28     /**
 29      * 传递的数组参数转换为堆的形状，放到data的数组中。
 30      * <p>
 31      * <p>
 32      * Heapify的算法复杂度，将n个元素逐个插入到一个空堆中，算法复杂度是O(nlogn)级别的。
 33      * <p>
 34      * <p>
 35      * 如果使用的是heapify的过程，算法复杂度是O(n)级别的。
 36      *
 37      * @param arr
 38      */
 39     public MaxHeap(E[] arr) {
 40         // 首先拷贝一份用户传递的数组元素，放入到动态数组中。
 41         // 根据传递的数组，生成一个新的动态数组
 42         data = new Array<>(arr);
 43         // 此时data已经存放了用户传递的arr数组元素的值
 44 
 45         // 从最后一个非叶子节点开始向前依次遍历，进行元素的下沉
 46         // 从最后一个非叶子节点开始，最后一个节点的索引的父亲节点的索引。
 47         for (int k = this.parent(arr.length - 1); k >= 0; k--) {
 48             this.siftDown(k);
 49         }
 50     }
 51 
 52     /**
 53      * 无参构造函数，如果不知道动态数组的大小，默认大小长度是10
 54      */
 55     public MaxHeap() {
 56         data = new Array<>();
 57     }
 58 
 59     /**
 60      * 返回堆中的元素个数
 61      *
 62      * @return
 63      */
 64     public int size() {
 65         return data.getSize();
 66     }
 67 
 68     /**
 69      * 返回一个布尔值，表示堆中是否为空
 70      *
 71      * @return
 72      */
 73     public boolean isEmpty() {
 74         return data.isEmpty();
 75     }
 76 
 77     /**
 78      * 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
 79      *
 80      * @param index
 81      * @return
 82      */
 83     private int parent(int index) {
 84         if (index == 0) {
 85             throw new IllegalArgumentException("index-0 doesn't hava parent.");
 86         }
 87         return (index - 1) / 2;
 88     }
 89 
 90     /**
 91      * 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引。
 92      *
 93      * @param index
 94      * @return
 95      */
 96     private int leftChild(int index) {
 97         return index * 2 + 1;
 98     }
 99 
100     /**
101      * 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引。
102      *
103      * @param index
104      * @return
105      */
106     private int rightChild(int index) {
107         return index * 2 + 2;
108     }
109 
110 
111     /**
112      * 向堆中添加元素。时间复杂度是O(logn)
113      *
114      * @param e
115      */
116     public void add(E e) {
117         // 向动态数组中添加一个元素
118         data.addLast(e);
119 
120         // 开始维护堆的性质
121         // 参数是，希望上浮的那个元素所对应的索引是多少，即最后一个元素的索引
122         siftUp(data.getSize() - 1);
123     }
124 
125     /**
126      * 元素上浮过程
127      *
128      * @param k
129      */
130     private void siftUp(int k) {
131         // 首先，不能已经达到了根节点，所以k必须大于零的。
132         // 如果该节点的父亲节点小于当前节点就进行上浮操作
133         while (k > 0 && data.get(this.parent(k)).compareTo(data.get(k)) < 0) {
134             // 将当前节点所处的元素和父亲节点的元素进行比较
135             // 如果当前节点所处的元素大于父亲节点的元素的值，将它们进行交换，进行上浮的动作。
136             data.swap(k, this.parent(k));
137             // 此时，让该节点元素的父亲节点的索引赋值给当前元素，
138             // 下一轮循环的时候，可以看当前的k已经来到了新的位置，
139             // 对于新的位置，是不是依然不满足堆的性质，就是它在新的位置
140             // 上的父亲节点所在的元素还要大，还要大就进行交换，依次类推。
141             // 直到走到了索引为0或者该节点小于父亲节点的元素。
142             k = parent(k);
143         }
144     }
145 
146     /**
147      * 看堆中的最大元素
148      *
149      * @return
150      */
151     public E findMax() {
152         if (data.getSize() == 0) {
153             throw new IllegalArgumentException("Can not findMax when heap is empty.");
154         }
155         return data.get(0);
156     }
157 
158     /**
159      * 取出堆中最大元素。时间复杂度是O(logn)
160      *
161      * @return
162      */
163     public E extractMax() {
164         // 首先，保存堆中的最大元素，暂存最大元素
165         E ret = this.findMax();
166         // 将堆顶元素和最后一个元素交换位置
167         data.swap(0, data.getSize() - 1);
168         // 交换完位置之后，此时已经将堆顶的元素放到数组的末尾了，数组末尾元素放在了堆顶位置
169 
170         // 删除最大元素，删除处于数组末尾的堆顶元素
171         data.removeLast();
172 
173         // 开始进行元素的下沉，参数是索引位置为0
174         siftDown(0);
175 
176         // 将最大元素返回，然后将最大元素从堆中删除
177         return ret;
178     }
179 
180     /**
181      * @param k 索引K
182      */
183     private void siftDown(int k) {
184         // 循环遍历，什么时候结束呢，
185         // 最极端的情况，k这个位置所处的节点，已经没有孩子了，当下沉到叶子节点的时候就结束了，
186         // 即，如果对于k这个节点的左孩子所在的索引小于数组的长度的时候，
187         // 此时k的左孩子都已经越界了，肯定一个孩子都没有了，此时右孩子的索引比左孩子的索引大。
188         // 循环的意思是，如果左孩子小于数组长度，就一直循环，否则就终止循环。
189         while (leftChild(k) < data.getSize()) {
190             // 比较k这个节点和k的左右孩子中最大的那个节点，看看k和这个最大的节点到底那个比较大，
191             // 先找到k左右孩子中最大的节点。
192             // 左孩子肯定是存在的，因为leftChild(k)小于数组的长度。
193             int j = this.leftChild(k);
194             // 但是右孩子不一定存在，所以此时进行判断，j + 1就是k的右孩子所在的索引，
195             // 如果K的右孩子小于数组的长度，说明有右孩子。
196             // 如果k的右孩子大于k的左孩子
197             if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
198                 // data[j]是leftChild和rightChild中的最大值
199                 // j自增。此时j存储的是右孩子所对应的索引了。
200                 // j++;
201                 j = rightChild(k);
202                 // 如果k没有右孩子，或者k的左孩子大于右孩子，那么j存储的就是左孩子所对应的索引。
203             }
204 
205 
206             // 此时，将k节点和左右孩子最大的节点进行比较，如果发现了就终止本次循环。
207             // 因为此时，父亲节点的值大于左右孩子的值了，下沉操作结束了。
208             if (data.get(k).compareTo(data.get(j)) >= 0) {
209                 break;
210             }
211 
212             // 否则，就开始交换k这个索引位置和j这个索引位置的值。
213             data.swap(k, j);
214             // 交换结束之后，将j的赋值给k。进行下一轮循环，对于新的一轮k来说，是否需要继续下沉。
215             k = j;
216         }
217 
218     }
219 
220 
221     /**
222      * 取出堆中的最大元素，并且替换成元素e。
223      * <p>
224      * <p>
225      * Replace是取出最大元素后，放入一个新元素。此时，堆中元素的总数未发生改变，
226      * 此时可以使用这样方法来实现，首先可以先extractMax，然后再add操作，
227      * 两次O(logn)的操作。但是呢，可以直接将堆顶元素替换以后Sift Down（元素进行下沉操作），
228      * 这样的话是一次O(logn)的操作。
229      *
230      * @param e
231      * @return
232      */
233     public E replace(E e) {
234         // 取出最大元素的值
235         E ret = findMax();
236         // 此时，将0索引位置的元素替换成e
237         data.set(0, e);
238         // 然后使用下沉元素，使得根节点元素符合堆的性质
239         siftDown(0);
240 
241         // 将最大元素的值返回
242         return ret;
243     }
244 
245 
246     /**
247      * 对使用heapify或者不使用的时候进行性能测试
248      * <p>
249      * 使用heapify的方式进行元素添加，或者自己将元素添加到空堆中。
250      *
251      * @param data
252      * @param isHeapify 是否使用heapify
253      * @return
254      */
255     private static double performanceTesting(Integer[] data, boolean isHeapify) {
256         // 创建一个变量存储开始时间
257         long startTime = System.nanoTime();
258 
259         // 创建一个变量
260         MaxHeap<Integer> maxHeap;
261         // 判断是否使用heapify
262         if (isHeapify) {
263             // true是使用heapify，此时将数组传入到构造函数中就实现了使用heapify方法
264             maxHeap = new MaxHeap<>(data);
265         } else {
266             // 创建一个maxHeap对象
267             maxHeap = new MaxHeap<>();
268             // 循环遍历，将所有的元素值都新增到堆中
269             for (int i = 0; i < data.length; i++) {
270                 maxHeap.add(data[i]);
271             }
272         }
273 
274         // 验证堆的正确性
275         // 创建一个一百万长度的数组arr
276         int[] arr = new int[data.length];
277         // 取出最大元素。此时是循环一百万次，是对堆进行了一遍排序，从大到小进行排序的。
278         for (int i = 0; i < data.length; i++) {
279             // 将堆中最大的元素依次放入到数组中
280             arr[i] = maxHeap.extractMax();
281         }
282 
283         // 循环判断，如果下一个元素的值小于这个元素，就抛出异常
284         // 即前一个数小于后一个数，此时不是降序的序列了。
285         for (int i = 1; i < data.length; i++) {
286             if (arr[i - 1] < arr[i]) {
287                 throw new IllegalArgumentException("Error");
288             }
289         }
290 
291         // 如果是降序数组，此时正常执行这句话
292         System.out.println("Test MaxHeap completed.");
293 
294         // 创建一个变量存储结束时间
295         long endTime = System.nanoTime();
296         // 将纳秒转换为秒返回即可
297         return (endTime - startTime) / 1000000000.0;
298     }
299 
300 
301     public static void main(String[] args) {
302 //        // 初始化一百万
303 //        int n = 1000000;
304 //        // 初始化堆
305 //        MaxHeap<Integer> maxHeap = new MaxHeap<>();
306 //        // 创建一个随机对象
307 //        Random random = new Random();
308 //        // 将一百万个随机数扔到堆中
309 //        for (int i = 0; i < n; i++) {
310 //            // 0-到Integet最大值
311 //            maxHeap.add(random.nextInt(Integer.MAX_VALUE));
312 //        }
313 //
314 //        // 创建一个一百万长度的数组arr
315 //        int[] arr = new int[n];
316 //        // 取出最大元素。此时是循环一百万次，是对堆进行了一遍排序，从大到小进行排序的。
317 //        for (int i = 0; i < n; i++) {
318 //            // 将堆中最大的元素依次放入到数组中
319 //            arr[i] = maxHeap.extractMax();
320 //        }
321 //
322 //        // 循环判断，如果下一个元素的值小于这个元素，就抛出异常
323 //        // 即前一个数小于后一个数，此时不是降序的序列了。
324 //        for (int i = 1; i < n; i++) {
325 //            if (arr[i - 1] < arr[i]) {
326 //                throw new IllegalArgumentException("Error");
327 //            }
328 //        }
329 //
330 //        System.out.println("Test MaxHeap completed.");
331 
332 
333         // 初始化一百万
334         int n = 1000000;
335         // 初始化数组
336         Integer[] data = new Integer[n];
337         // 创建一个随机对象
338         Random random = new Random();
339         // 将一百万个随机数扔到堆中
340         for (int i = 0; i < n; i++) {
341             // 0-到Integet最大值
342             data[i] = random.nextInt(Integer.MAX_VALUE);
343         }
344 
345         // 第一次使用的是一个一个元素新增到堆中
346         double time1 = MaxHeap.performanceTesting(data, false);
347         System.out.println("Without heapify time1 : " + time1);
348 
349         // 第二次使用heapify的方式将元素添加到堆中
350         double time2 = MaxHeap.performanceTesting(data, true);
351         System.out.println("with heapify time2 : " + time2);
352 
353     }
354 
355 }

 1 package com.queue;
 2 
 3 import com.maxHeap.MaxHeap;
 4 
 5 /**
 6  * 优先队列的底层实现可以使用最大堆进行实现，
 7  * 由于优先队列本身就是一个队列，所以可以复用队列的接口。
 8  *
 9  * @param <E> 由于优先队列要具有可比较性，所以要进行继承Comparable
10  */
11 public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
12 
13     // 使用最大堆实现优先队列
14     private MaxHeap<E> maxHeap;
15 
16     /**
17      * 无参构造函数，直接创建一个MaxHeap即可
18      */
19     public PriorityQueue() {
20         maxHeap = new MaxHeap<>();
21     }
22 
23     @Override
24     public void enqueue(E e) {
25         // 入队操作，直接调用最大堆的add方法
26         maxHeap.add(e);
27     }
28 
29     @Override
30     public E dequeue() {
31         // 出队操作，将最大元素提取出来
32         return maxHeap.extractMax();
33     }
34 
35     @Override
36     public E getFront() {
37         // 查看队首的元素是谁
38         // 其实对应的是最大堆对应的堆顶的元素
39         E maxHeapMax = maxHeap.findMax();
40         // 获取到队列中队首的元素。对应栈的查看栈顶的元素。
41         return maxHeapMax;
42     }
43 
44     @Override
45     public int getSize() {
46         // 直接返回最大堆中的大小
47         return maxHeap.size();
48     }
49 
50     @Override
51     public boolean isEmpty() {
52         // 直接返回最大堆中的是否为空
53         return maxHeap.isEmpty();
54     }
55 
56 
57     public static void main(String[] args) {
58         PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
59         // 优先队列入队操作
60         for (int i = 0; i < 1000; i++) {
61             priorityQueue.enqueue(i);
62         }
63 
64 
65         // 优先队列出队操作
66         for (int i = 0; i < 1000; i++) {
67             if (i % 30 == 0) {
68                 System.out.println();
69             }
70             System.out.print(priorityQueue.dequeue() + " ");
71         }
72 
73 
74     }
75 
76 }