快捷導(dǎo)航

Java中優(yōu)先隊列PriorityQueue常用方法示例

更新時間：2023年09月23日 10:37:10 作者：little_fat_sheep

這篇文章主要介紹了Java中優(yōu)先隊列PriorityQueue常用方法示例,PriorityQueue是一種特殊的隊列,滿足隊列的“隊尾進(jìn)、隊頭出”條件,但是每次插入或刪除元素后,都對隊列進(jìn)行調(diào)整,使得隊列始終構(gòu)成最小堆(或最大堆),需要的朋友可以參考下

1 前言

PriorityQueue是一種特殊的隊列，滿足隊列的“隊尾進(jìn)、隊頭出”條件，但是每次插入或刪除元素后，都對隊列進(jìn)行調(diào)整，使得隊列始終構(gòu)成最小堆（或最大堆）。具體調(diào)整如下：

插入元素后，從堆底到堆頂調(diào)整堆；
刪除元素后，將隊尾元素復(fù)制到隊頭，并從堆頂?shù)蕉训渍{(diào)整堆。

PriorityQueue采用數(shù)組實現(xiàn)，也是一棵完全二叉樹，構(gòu)成堆結(jié)構(gòu)。數(shù)組初始大小為11。

Queue框架如下：

Queue框架

2 PriorityQueue常用方法

public boolean add(E e); //在隊尾添加元素，并調(diào)整堆結(jié)構(gòu)
public E remove(); //在隊頭刪除元素，并返回，再調(diào)整堆結(jié)構(gòu)
public E element(); //返回隊頭元素（不刪除）
public boolean isEmpty(); //判斷隊列是否為空
public int size(); //獲取隊列中元素個數(shù)
public void clear(); //清空隊列
public boolean contains(Object o); //判斷隊列中是否包含指定元素（從隊頭到隊尾遍歷）
public Iterator<E> iterator(); //迭代器

3 簡單案例

3.1 最小優(yōu)先隊列

import java.util.PriorityQueue;
public class Main {
	static int[] a={6,4,7,3,9,8,1,2,5,0};
	public static void main(String[] args) {
		fun();
	}
	static void fun() {
		PriorityQueue<Integer> que=new PriorityQueue<Integer>();
		for(int e:a) {
			que.add(e);
		}
		for(int e:que) {
			System.out.print(e+" ");
		}
		System.out.println();
		while(!que.isEmpty()) {
			int e=que.remove();
			System.out.print(e+" ");
		}
	}
}

運行結(jié)果：

0 1 3 4 2 8 7 6 5 9
0 1 2 3 4 5 6 7 8 9

堆結(jié)構(gòu)：

最小優(yōu)先隊列內(nèi)部堆結(jié)構(gòu)

3.2 最大優(yōu)先隊列

import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
	static int[] a={6,4,7,3,9,8,1,2,5,0};
	public static void main(String[] args) {
		fun();
	}
	static void fun() {
		PriorityQueue<Integer> que=new PriorityQueue<Integer>(new Comparator<Integer>() {
			public int compare(Integer o1, Integer o2) {				
				return o2-o1;
			}
		});
		for(int e:a) {
			que.add(e);
		}
		for(int e:que) {
			System.out.print(e+" ");
		}
		System.out.println();
		while(!que.isEmpty()) {
			int e=que.remove();
			System.out.print(e+" ");
		}
	}
}

運行結(jié)果：

9 7 8 5 4 6 1 2 3 0
9 8 7 6 5 4 3 2 1 0

堆結(jié)構(gòu)：

最大優(yōu)先隊列內(nèi)部堆結(jié)構(gòu)

3.3 topK問題

topK問題是指：從海量數(shù)據(jù)中尋找最大的前k個數(shù)據(jù)，比如從1億個數(shù)據(jù)中，尋找最大的1萬個數(shù)。

使用優(yōu)先隊列，能夠很好的解決這個問題。先使用前1萬個數(shù)構(gòu)建最小優(yōu)先隊列，以后每取一個數(shù)，都與隊頭元素進(jìn)行比較，若大于隊頭元素，就將隊頭元素刪除，并將該元素添加到優(yōu)先隊列中；若小于隊頭元素，則將該元素丟棄掉。如此往復(fù)，直至所有元素都訪問完。最后優(yōu)先隊列中的1萬個元素就是最大的1萬個元素。

為方便實驗，這里以求 {6,4,7,3,9,8,1,2,5,0} 中最大的5個數(shù)為例。

import java.util.PriorityQueue;
public class Main {
	static int[] a={6,4,7,3,9,8,1,2,5,0};
	public static void main(String[] args) {
		fun();
	}
	static void fun() {
		PriorityQueue<Integer> que=new PriorityQueue<Integer>();
		for(int i=0;i<5;i++) {
			que.add(a[i]);
		}
		for(int i=5;i<10;i++) {
			if(a[i]>que.element()) {
				que.remove();
				que.add(a[i]);
			}
		}
		while(!que.isEmpty()) {
			int e=que.remove();
			System.out.print(e+" ");
		}
	}
}

運行結(jié)果：