堆（优先级队列 PriorityQueue）

GeekLiHua

发布于 2025-01-21 07:48:17

10300

代码可运行

文章被收录于专栏：JavaJava

运行总次数：0

代码可运行

堆（优先级队列 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]*/
	}