快捷導(dǎo)航

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

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

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

1 前言

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

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

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

Queue框架如下：

Queue框架

2 PriorityQueue常用方法

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

3 簡單案例

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

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+" ");
		}
	}
}

運(yùn)行結(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)先隊(duì)列內(nèi)部堆結(jié)構(gòu)

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

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+" ");
		}
	}
}

運(yùn)行結(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)先隊(duì)列內(nèi)部堆結(jié)構(gòu)

3.3 topK問題

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

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

為方便實(shí)驗(yàn)，這里以求 {6,4,7,3,9,8,1,2,5,0} 中最大的5個(gè)數(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+" ");
		}
	}
}

運(yùn)行結(jié)果：

5 6 7 8 9

到此這篇關(guān)于Java中優(yōu)先隊(duì)列PriorityQueue常用方法示例的文章就介紹到這了,更多相關(guān)優(yōu)先隊(duì)列PriorityQueue常用方法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: