Java集合教程 - Java優(yōu)先級隊列

優(yōu)先級隊列是其中每個元素具有相關(guān)聯(lián)的優(yōu)先級的隊列。具有最高優(yōu)先級的元素將從隊列中刪除。

PriorityQueue 是一個實現(xiàn)類對于Java Collection Framework中的無界優(yōu)先級隊列。

我們可以使用在每個元素中實現(xiàn)的 Comparable 接口作為其優(yōu)先事項。

或者我們可以提供一個 Comparator 對象，這將確定元素的優(yōu)先級順序。

當(dāng)向優(yōu)先級隊列添加新元素時，它將根據(jù)其優(yōu)先級位于隊列中。

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

上面的代碼生成以下結(jié)果。

注意

當(dāng)您使用迭代器時， PriorityQueue 類不保證元素的任何順序。

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

以下代碼顯示如何使用 Comparator 對象為ComparablePerson列表創(chuàng)建優(yōu)先級隊列。

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

上面的代碼生成以下結(jié)果。