堆（优先级队列 PriorityQueue）-蒲公英云

堆（优先级队列 PriorityQueue）

通过题目讲解

题目链接博客：合并果子(优先级队列)
在这里插入图片描述

提交代码

import java.io.*;
import java.util.*;
public class Main
{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        int n = in.nextInt();
        for (int i = 0; i < n; ++ i)
        {
            q.add(in.nextInt());
        }
        int sum = 0;
        while(q.size()>1)
        {
            int a = q.poll();
            int b = q.poll();
            sum += a + b;
            q.add(a + b);
        }
        System.out.println(sum);
    }
}

常用方法

和Queue一样
参考文档：队列(Queue)

遍历方式

public static void main(String[] args) {
        PriorityQueue<Integer> pqueue = new PriorityQueue<Integer>();            
        pqueue.add(100);
        pqueue.add(10);
        pqueue.add(11);
        pqueue.add(1);
        pqueue.add(646);
        System.out.println(pqueue);
        /*[1, 10, 11, 100, 646]*/
        for (Integer it : pqueue)
        {
            System.out.print(it + " ");
        }
        /*1 10 11 100 646 */
        System.out.println();
        Iterator<Integer> it = pqueue.iterator();
        while(it.hasNext())
        {
            System.out.print(it.next() + " ");
        }
        /*1 10 11 100 646 */
    }

排序

public static void main(String[] args) {
        // 默认排序规则是升序排列
        // 可以自定义排序规则
        PriorityQueue<Integer> pqueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                int num = 0;
                if (o1 > o2) num = -1;
                else num = 1;
                return num;
            }
        });            
        pqueue.add(100);
        pqueue.add(10);
        pqueue.add(11);
        pqueue.add(1);
        pqueue.add(646);
        System.out.println(pqueue);
        /*[646, 100, 11, 1, 10]*/
    }