编程教育资源分享平台

网站首页 > 后端开发 正文

Java优先级队列

luoriw 2024-02-01 14:27:36 后端开发 11 ℃ 0 评论

优先级队列是其中每个元素具有相关联的优先级的队列。具有最高优先级的元素将从队列中删除。

PriorityQueue 是一个实现类对于Java Collection Framework中的无界优先级队列。

我们可以使用在每个元素中实现的 Comparable 接口作为其优先事项。

或者我们可以提供一个 Comparator 对象,这将确定元素的优先级顺序。

当向优先级队列添加新元素时,它将根据其优先级位于队列中。

PriorityQueue APIs

例子

import java.util.PriorityQueue;
import java.util.Queue;
class ComparablePerson implements Comparable<ComparablePerson> {
 private int id;
 private String name;
 public ComparablePerson(int id, String name) {
 this.id = id;
 this.name = name;
 }
 public int getId() {
 return id;
 }
 public void setId(int id) {
 this.id = id;
 }
 public String getName() {
 return name;
 }
 public void setName(String name) {
 this.name = name;
 }
 @Override
 public boolean equals(Object o) {
 if (!(o instanceof ComparablePerson)) {
 return false;
 }
 ComparablePerson p = (ComparablePerson) o;
 if (this.id == p.getId()) {
 return true;
 }
 return false;
 }
 @Override
 public int hashCode() {
 return this.id;
 }
 @Override
 public String toString() {
 return "(" + id + ", " + name + ")";
 }
 @Override
 public int compareTo(ComparablePerson cp) {
 int cpId = cp.getId();
 String cpName = cp.getName();
 if (this.getId() < cpId) {
 return -1;
 }
 if (this.getId() > cpId) {
 return 1;
 }
 if (this.getId() == cpId) {
 return this.getName().compareTo(cpName);
 }
 
 // Should not reach here 
 return 0;
 }
}
public class Main {
 public static void main(String[] args) {
 Queue<ComparablePerson> pq = new PriorityQueue<>();
 pq.add(new ComparablePerson(1, "Oracle"));
 pq.add(new ComparablePerson(4, "XML"));
 pq.add(new ComparablePerson(2, "HTML"));
 pq.add(new ComparablePerson(3, "CSS"));
 pq.add(new ComparablePerson(4, "Java"));
 System.out.println(pq);
 while (pq.peek() != null) {
 System.out.println("Head Element: " + pq.peek());
 pq.remove();
 System.out.println("Priority queue: " + pq);
 }
 }
}

上面的代码生成以下结果。

注意

当您使用迭代器时, PriorityQueue 类不保证元素的任何顺序。

它的toString()方法使用它的迭代器给你的元素的字符串表示。

以下代码显示如何使用 Comparator 对象为ComparablePerson列表创建优先级队列。

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
class ComparablePerson implements Comparable<ComparablePerson> {
 private int id;
 private String name;
 public ComparablePerson(int id, String name) {
 this.id = id;
 this.name = name;
 }
 public int getId() {
 return id;
 }
 public void setId(int id) {
 this.id = id;
 }
 public String getName() {
 return name;
 }
 public void setName(String name) {
 this.name = name;
 }
 @Override
 public boolean equals(Object o) {
 if (!(o instanceof ComparablePerson)) {
 return false;
 }
 ComparablePerson p = (ComparablePerson) o;
 if (this.id == p.getId()) {
 return true;
 }
 return false;
 }
 @Override
 public int hashCode() {
 return this.id;
 }
 @Override
 public String toString() {
 return "(" + id + ", " + name + ")";
 }
 @Override
 public int compareTo(ComparablePerson cp) {
 int cpId = cp.getId();
 String cpName = cp.getName();
 if (this.getId() < cpId) {
 return -1;
 }
 if (this.getId() > cpId) {
 return 1;
 }
 if (this.getId() == cpId) {
 return this.getName().compareTo(cpName);
 }
 // Should not reach here
 return 0;
 }
}
public class Main {
 public static void main(String[] args) {
 int initialCapacity = 5;
 Comparator<ComparablePerson> nameComparator = Comparator
 .comparing(ComparablePerson::getName);
 Queue<ComparablePerson> pq = new PriorityQueue<>(initialCapacity,
 nameComparator);
 pq.add(new ComparablePerson(1, "Oracle"));
 pq.add(new ComparablePerson(4, "XML"));
 pq.add(new ComparablePerson(2, "HTML"));
 pq.add(new ComparablePerson(3, "CSS"));
 pq.add(new ComparablePerson(4, "Java"));
 System.out.println("Priority queue: " + pq);
 while (pq.peek() != null) {
 System.out.println("Head Element: " + pq.peek());
 pq.remove();
 System.out.println("Removed one element from Queue");
 System.out.println("Priority queue: " + pq);
 }
 }
}

上面的代码生成以下结果。

Tags:

本文暂时没有评论,来添加一个吧(●'◡'●)

欢迎 发表评论:

最近发表
标签列表
最新留言