java集合PriorityQueue優(yōu)先級隊列方法實(shí)例

更新時間：2023年12月20日 10:40:59 作者：bug生產(chǎn)者

這篇文章主要為大家介紹了java集合PriorityQueue優(yōu)先級隊列方法實(shí)例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

PriorityQueue詳解

PriorityQueue是優(yōu)先級隊列，底層使用數(shù)組存儲，是基于二叉堆的一個無界隊列，可以使用默認(rèn)排序或者提供Comparator比較器使得隊列中的元素有序

存儲結(jié)構(gòu)

小頂堆

根節(jié)點(diǎn)的元素最小是小頂堆(小于左右子節(jié)點(diǎn)的值)

大頂堆

根節(jié)點(diǎn)的元素最大是大頂堆(大于左右子節(jié)點(diǎn)的值)

源碼分析

重要屬性

// 默認(rèn)的初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
 * 使用數(shù)組存放  是一個平衡二叉堆，對于queue[n]有兩個子節(jié)點(diǎn)queue[2*n+1] 和 queue[2*(n+1)]
 */
transient Object[] queue; // non-private to simplify nested class access
/**
 * 優(yōu)先隊列中的元素個數(shù)
 */
private int size = 0;
/**
 * 比較器，如果為null，為使用默認(rèn)的自然排序
 */
private final Comparator<? super E> comparator;
/**
 * 修改次數(shù)
 */
transient int modCount = 0; // non-private to simplify nested class access
/**
* 最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

構(gòu)造器

public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}
public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}
public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator) {
    // Note: This restriction of at least one is not actually needed,
    // but continues for 1.5 compatibility
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}
@SuppressWarnings("unchecked")
public PriorityQueue(Collection<? extends E> c) {
    if (c instanceof SortedSet<?>) {
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        initElementsFromCollection(ss);
    }
    else if (c instanceof PriorityQueue<?>) {
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        initFromPriorityQueue(pq);
    }
    else {
        this.comparator = null;
        initFromCollection(c);
    }
}
@SuppressWarnings("unchecked")
public PriorityQueue(PriorityQueue<? extends E> c) {
    this.comparator = (Comparator<? super E>) c.comparator();
    initFromPriorityQueue(c);
}
@SuppressWarnings("unchecked")
public PriorityQueue(SortedSet<? extends E> c) {
    this.comparator = (Comparator<? super E>) c.comparator();
    initElementsFromCollection(c);
}

常用方法

獲取頂端元素

// 直接取數(shù)組中的第一個元素就是頂端元素
public E peek() {
    return (size == 0) ? null : (E) queue[0];
}

插入

以使用默認(rèn)比較器為例

// add方法直接調(diào)用offer方法，往數(shù)組末尾添加元素
public boolean add(E e) {
    return offer(e);
}
public boolean offer(E e) {
  if (e == null)
    throw new NullPointerException();
  modCount++;
  int i = size;
  // 看一下數(shù)組容量是否足夠
  if (i >= queue.length) // 不夠則擴(kuò)容
    grow(i + 1);
  size = i + 1;
  if (i == 0) // 首次添加，將元素放到頂端即可
    queue[0] = e;
  else
    siftUp(i, e);
  return true;
}
// 傳入的minCapacity為插入該數(shù)據(jù)所需要的最小容量
private void grow(int minCapacity) {
  int oldCapacity = queue.length;
  // 如果原始容量小于64，則容量加2，否則容量增加50%
  int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                   (oldCapacity + 2) :
                                   (oldCapacity >> 1));
  // overflow-conscious code
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    // 如果擴(kuò)容之后的容量大于MAX_ARRAY_SIZE,則比較所需要的容量和MAX_ARRAY_SIZE的大小  
    //(minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    newCapacity = hugeCapacity(minCapacity);
  queue = Arrays.copyOf(queue, newCapacity);
}
private void siftUp(int k, E x) {
  if (comparator != null) // 使用自定義選擇器
    siftUpUsingComparator(k, x);
  else // 使用默認(rèn)的自然排序，默認(rèn)的排序?yàn)樾№敹?
    siftUpComparable(k, x);
}
// 存放數(shù)據(jù)的核心代碼
// k為所要存放的索引位置，x為元素
private void siftUpComparable(int k, E x) {
  Comparable<? super E> key = (Comparable<? super E>) x;
  while (k > 0) {
    int parent = (k - 1) >>> 1; // 左移一位找到父節(jié)點(diǎn)的位置
    Object e = queue[parent];// 父節(jié)點(diǎn)元素
    if (key.compareTo((E) e) >= 0) // 比較該元素和父節(jié)點(diǎn)元素大小,如果該節(jié)點(diǎn)大，則跳出循環(huán)
      break;
    queue[k] = e; // 將父節(jié)點(diǎn)的值存到k索引位置
    k = parent; // 索引位置變成父節(jié)點(diǎn)的索引位置，繼續(xù)對比父節(jié)點(diǎn)的父節(jié)點(diǎn)
  }
  queue[k] = key;
}

刪除

還是以默認(rèn)的比較器為例

public boolean remove(Object o) {
      // 找到該對象對應(yīng)的索引位置
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}
// 找到該對象對應(yīng)的索引位置
private int indexOf(Object o) {
  if (o != null) {
    for (int i = 0; i < size; i++)
      if (o.equals(queue[i]))
        return i;
  }
  return -1;
}
private E removeAt(int i) {
  // assert i >= 0 && i < size;
  modCount++;
  int s = --size;
  // 尾結(jié)點(diǎn)
  if (s == i) // removed last element
    queue[i] = null;
  else {
    // 尾結(jié)點(diǎn)的元素
    E moved = (E) queue[s];
    // 將尾結(jié)點(diǎn)置空
    queue[s] = null;
    siftDown(i, moved);
    // 沒有進(jìn)while循環(huán)時(表示在siftDown()方法中直接走到queue[k] = key;),刪除節(jié)點(diǎn)沒有子節(jié)點(diǎn)，開始向上查找
    // 向上查找的原因是因?yàn)榭赡芩鶆h除的節(jié)點(diǎn)與尾結(jié)點(diǎn)處于不同的子樹下
    if (queue[i] == moved) {
      siftUp(i, moved);
      if (queue[i] != moved)
        return moved;
    }
  }
  return null;
}
// k為所要刪除的元素位置  x為尾結(jié)點(diǎn)元素
private void siftDown(int k, E x) {
  if (comparator != null)
    siftDownUsingComparator(k, x);
  else
    siftDownComparable(k, x);
}
// k為所要移除的索引位置   x為尾結(jié)點(diǎn)元素
// 該方法為從刪除節(jié)點(diǎn)向下查找
private void siftDownComparable(int k, E x) {
  Comparable<? super E> key = (Comparable<? super E>)x;
  // 中間元素，判斷是否有子節(jié)點(diǎn)
  int half = size >>> 1;        // loop while a non-leaf
  while (k < half) {
    // 找到子節(jié)點(diǎn)
    int child = (k << 1) + 1; // assume left child is least
    Object c = queue[child];
    // 找到子節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
    int right = child + 1;
    // 子節(jié)點(diǎn)和子節(jié)點(diǎn)的兄弟節(jié)點(diǎn)中找到小的
    if (right < size &&
        ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
      c = queue[child = right];
    // 尾結(jié)點(diǎn)元素小于子節(jié)點(diǎn)元素，結(jié)束循環(huán)
    if (key.compareTo((E) c) <= 0)
      break;
    // 繼續(xù)向下查找
    queue[k] = c;
    k = child;
  }
  //跳出循環(huán)的條件是尾結(jié)點(diǎn)元素大于子節(jié)點(diǎn)元素了，所以將尾結(jié)點(diǎn)元素放到k索引位置
  queue[k] = key;
}
// k為要刪除的索引位置  x為尾結(jié)點(diǎn)元素
private void siftUp(int k, E x) {
  if (comparator != null)
    siftUpUsingComparator(k, x);
  else
    siftUpComparable(k, x);
}
// k為要刪除的索引位置  x為尾結(jié)點(diǎn)元素
// 從刪除索引位置開始向上查找
private void siftUpComparable(int k, E x) {
  Comparable<? super E> key = (Comparable<? super E>) x;
  while (k > 0) {
    // 找到父節(jié)點(diǎn)
    int parent = (k - 1) >>> 1;
    Object e = queue[parent];
    // 尾結(jié)點(diǎn)大于父節(jié)點(diǎn)，直接跳出循環(huán)
    if (key.compareTo((E) e) >= 0)
      break;
    // 繼續(xù)向上查找
    queue[k] = e;
    k = parent;
  }
  queue[k] = key;
}

以上就是java集合PriorityQueue優(yōu)先級隊列方法實(shí)例的詳細(xì)內(nèi)容，更多關(guān)于java集合PriorityQueue的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: