Java堆结构PriorityQueue

￡神魔★判官ぃ 2021-09-26 15:14 379阅读 0赞

在Java1.5中引入了PriorityQueue（优先队列），PriorityQueue默认实现了最小堆，也可以传入Comparetor来实现最大堆。  
实验代码如下：

import java.util.Comparator;
    import java.util.PriorityQueue;
    
    public class PriorityQueueDemo { 
    
        /** * @param args */
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            //优先队列的使用 默认实现的是最小堆
            PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>();
            pQueue.add(12);
            pQueue.add(56);
            pQueue.add(2);
            pQueue.add(34);
            pQueue.add(89);
            System.out.println("*****打印最小堆****");
            for (Integer integer : pQueue) {
                System.out.print(integer+" ");
            }
            System.out.println();
            System.out.println("*****最小堆依次出队列（升序）****");
            while(!pQueue.isEmpty()){
                System.out.print(pQueue.poll()+" ");
            }
            System.out.println();
            /**最大堆**/
            int initialCapacity = 100;
            PriorityQueue<Integer> pQueue1 = new PriorityQueue<Integer>(
                    initialCapacity,
                    new Comparator<Integer>(){
    
                        @Override
                        public int compare(Integer o1, Integer o2) {
                            // TODO Auto-generated method stub
                            //return 02 - o1;
                            if(o1>o2)
                                return -1;
                            if(o1<o2)
                                return 1;
                            return 0;
                        }
    
                    });
            pQueue1.add(12);
            pQueue1.add(56);
            pQueue1.add(2);
            pQueue1.add(34);
            pQueue1.add(89);
            System.out.println("*****打印最大堆****");
            for (Integer integer : pQueue1) {
                System.out.print(integer+" ");
            }
            System.out.println();
            System.out.println("*****最大堆依次出队列(降序)****");
            while(!pQueue1.isEmpty()){
                System.out.print(pQueue1.poll()+" ");
            }
        }
    
    }

实验结果：

*****打印最小堆****
    2 34 12 56 89 
    *****最小堆依次出队列****
    2 12 34 56 89 
    *****打印最大堆****
    89 56 2 12 34 
    *****最大堆依次出队列****
    89 56 34 12 2