堆（优先级队列 PriorityQueue）

╰+哭是因爲堅強的太久メ 2024-03-31 16:11 72阅读 0赞

## 堆（优先级队列 PriorityQueue） ##

### 通过题目讲解 ###

**题目链接博客**：[合并果子(优先级队列)][Link 1]  
![在这里插入图片描述][26fbcd19274c4828be038d1581cbd63f.png]

**提交代码**

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)  
][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]*/
    	}

[Link 1]: https://blog.csdn.net/qq_51447496/article/details/128212698
[26fbcd19274c4828be038d1581cbd63f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/bc92c308cc3d45afae74feb42e58e4c2.png
[Queue_]: https://blog.csdn.net/qq_51447496/article/details/127268911