PriorityQueue 源碼解析(四)

🍁 作者：知識淺談，CSDN部落格專家，阿裡雲簽約部落客，InfoQ簽約部落客，華為雲雲享專家

📌 擅長領域：全棧工程師、爬蟲、ACM算法

💒 公衆号：知識淺談

PriorityQueue 源碼解析(四)總結

正菜來了⛳⛳⛳

🎈PriorityQueue 源碼對應的函數

🍮boolean contains(Object o)

含義：這個函數的意思是檢視優先隊列中是否含有o這個元素，方法裡邊調用的還是indexOf這個函數。

public boolean contains(Object o) {  
     return indexOf(o) != -1;
}      

🍮Object[] toArray()

含義：傳回一個包含此隊列中所有元素的數組。元素沒有特定的順序，裡邊調用了Arrays.copyOf函數把優先對列中的數組克隆一個新數組出來。

public Object[] toArray() {
    return Arrays.copyOf(queue, size);
}      

🍮final class Itr

含義： 靜态内部類Itr，主要是用于實作疊代的使用，具體的内部的内容可以自行檢視。

private final class Itr implements Iterator<E> {
}      

🍮int size()

含義：因為優先隊列類中的size代表的是隊列中的元素個數，是以調用size（）函數會傳回目前優先隊列中的元素個數。

public int size() {
    return size;
}      

🍮void clear()

含義：這個clear的含義就是把queue[i]的指向都變為空，并把size變為0；

public void clear() {
    modCount++;
    for (int i = 0; i < size; i++)
        queue[i] = null;
    size = 0;
}      

🍮E poll()

含義：這個poll函數的意思是取出隊列頭部的元素并且把這個元素從隊列中删除。

@SuppressWarnings("unchecked")
public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);
    return result;
}      

🍮siftUp(int k, E x)

含義：這個函數的意思是在位置 k 處插入項 x，通過将 x 提升到樹上直到它大于或等于其父項或者是根來保持堆不變。簡化和加速強制和比較。 Comparable 和 Comparator 版本被分成不同的方法，這些方法在其他方面是相同的。 （對于 siftDown 也是如此。）

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}      

上邊的而函數調用了siftUpUsingComparator和siftUpComparable，我們接着看着兩個函數。

🍮siftUpComparable和siftUpUsingComparator(int k, E x)

含義：這個函數的意思是從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;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}      

🍮 void siftDown(int k, E x)

含義：在位置 k 處插入項 x，通過重複将 x 降級到樹下直到它小于或等于其子項或者是葉子來保持堆不變。

private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}      

🍮void heapify()

private void heapify() {
    for (int i = (size >>> 1) - 1; i >= 0; i--)
        siftDown(i, (E) queue[i]);
}      

🍚總結