PriorityQueue

Queue
PriorityQueue
- 1.PriorityQueue簡介
- 2.基本屬性
- 3.基本方法
- - （1）add(E e)和offer(E e)
  - （2）grow(int minCapacity)擴容
  - （3）siftUp(int k, E x) 上浮調整函數
  - （4）peek()
  - （5）remove(Object o)和poll()
  - （6）siftDown(int k, E x)

Queue

Queue是先入先出（FIFO）的一個隊列資料結構，可以分為阻塞隊列和非阻塞隊列。

接口方法：

//插入元素。成功時傳回true，如果失敗則抛出異常
boolean add(E e);
//插入元素。成功時傳回true，失敗傳回false
boolean offer(E e);
//檢索并删除隊列的頭部，如果隊列為空，則抛出異常
E remove();
//檢索并删除隊列的頭部，如果隊列為空，則傳回null
E poll();
//檢索但不删除隊列的頭部，如果隊列為空，則抛出異常
E element();
//檢索但不删除隊列的頭部，如果隊列為空，則傳回null
E peek();

安全的會進行容量檢查的（add、remove、element）

不安全的不進行容量控制的（offer、delete、peek）

PriorityQueue

優先隊列的作用是保證每次取出的元素都是隊列中權值最小的。

Java中的PriorityQueue實作了Queue接口，不允許放入null元素，通過二叉小頂堆實作，可以用以可完全二叉樹表示（具體說是通過完全二叉樹實作的小頂堆）。

完全二叉樹實作的小頂堆（任意一個非葉子節點的權值，都不大于其左右子節點的權值）。

二叉堆可以使用數組來表示，父子節點下标關系如下：

PriorityQueue優先隊列源碼解析QueuePriorityQueue

1.PriorityQueue簡介

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

繼承了AbstractQueue
實作了Serializable，可以實作序列化和反序列化

2.基本屬性

//序列化的UID
private static final long serialVersionUID = -7720805057305804111L;
//預設初始容量為11
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//存放資料的Object數組
transient Object[] queue; // non-private to simplify nested class access
//優先隊列中的元素個數
private int size = 0;
//比較器，如果優先級隊列使用元素的自然順序，則為 null（預設是自然排序）。
private final Comparator<? super E> comparator;
//優先隊列結構上的修改次數
transient int modCount = 0; // non-private to simplify nested class access

//建立一個具有預設初始容量 (11) 的PriorityQueue ，它根據元素的自然順序對其元素進行排序。
public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
}

PriorityQueue使用數組存儲資料，基于數組形式的小頂堆來做的。

PriorityQueue是在構造函數調用階段就已經申請了底層數組。而有的容器類比如HashMap則是采用懶加載機制，在實際的使用的時候才會真正的去申請底層的資料空間。hashMap在實際指定的初始容量的情況下，會去申請一個2的n次方的數值大小的空間，而Queue在預設的沒有指定初始容量的時候，就隻申請了長度為11的數組。ArrayList集合在沒有指定初始容量的時候，也是采用的類似懶加載的機制，指定一個長度為0的空數組，真正使用的時候才建立底層數組的空間。

3.基本方法

（1）add(E e)和offer(E e)

因為priority是無界隊列，是以添加元素不會抛出illegalStateException異常，如果目前數組已滿，則會直接擴容後插入。

public boolean add(E e) {
	//直接調用offer方法
    return offer(e);
}

public boolean offer(E e) {
		//前置檢驗，檢查插入元素是否為null，不允許插入null
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        //檢查數組容量，如果容量不夠，直接進行擴容。
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
        	//如果目前隊列為空，直接放到queue[0]
            queue[0] = e;
        else
        	//需要調整元素位置
            siftUp(i, e);
        return true;
    }

（2）grow(int minCapacity)擴容

如果目前容量小于64，則擴容目前容量+2，比如目前容量是15，則擴容後的容量為 15 + 15 + 2 = 32

如果目前容量大于等于64，則擴容目前容量的一半，比如目前容量是60 ，則擴容後的容量是 60 + 30 = 90

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}
//由于queue是一個無界數組，當擴容到一定程度時就會超出整型的最大值或者記憶體溢出，是以做一個限制處理
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
 }

（3）siftUp(int k, E x) 上浮調整函數

該代碼的實作其實是一個小頂堆的實作，即一個完全平衡二叉樹。每次往裡面添加節點的時候，先跟父節點比較大小，如果比父節點小，則需要跟父節點交換位置，然後繼續跟目前的父節點比較，直到完成最小元素的位置轉換。

private void siftUp(int k, E x) {
    if (comparator != null)
    	//非自然排序
        siftUpUsingComparator(k, x);
    else
    	//自然排序
        siftUpComparable(k, x);
}
//此方法中k就是插入元素的下标值，x是元素
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
    	//通過節點個數找到父節點的位置
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        //将目前要插入的節點與父節點先進行比較
        //如果大于父節點，直接執行 queue[k] = x; 将該元素放到最底部
        if (comparator.compare(x, (E) e) >= 0)
        	//上浮過程，直到元素x大于父節點，說明小頂堆到達了平衡
            break;
        //如果小于父節點，繼續向上比較，執行下一次循環
        queue[k] = e;
        k = parent;
    }
    queue[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;
}

（4）peek()

//擷取但不移除此隊列的頭，如果此隊列為空，則傳回null
public E peek() {
    return (size == 0) ? null : (E) queue[0];
}

（5）remove(Object o)和poll()

//擷取并移除隊列的頭部，如果隊列為空，則抛出異常
public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}
private E removeAt(int i) {
        // assert i >= 0 && i < size;
        modCount++;
        int s = --size;
        if (s == i) // removed last element
            queue[i] = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;
            siftDown(i, moved);
            if (queue[i] == moved) {
                siftUp(i, moved);
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
}

//擷取并移除此隊列的頭，如果隊列為空，則傳回null
public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    //取出隊頭元素
    E result = (E) queue[0];
    //儲存隊尾元素
    E x = (E) queue[s];
    //同時将隊尾元素置為null
    queue[s] = null;
    //如果queue還有元素存在，調節二叉樹中的元素位置
    if (s != 0)
        siftDown(0, x);
    return result;
}

（6）siftDown(int k, E x)

取k位置左邊子節點c（如果右子節點存在并且小于左子節點，則值應該是右邊的值），跟E比較，如果大于E，則queue[k] = E 完成，否則queue[k] = c ，k指派為c的節點的位置，重複開始的比較，直到周遊了所有左邊子節點。

簡單來說，就是poll之後去除頭節點，将尾節點放在合适的位置上，使之重新成為完全平衡二叉樹。

private void siftDown(int k, E x) {
    if (comparator != null)
    	//非自然排序
        siftDownUsingComparator(k, x);
    else
    	//自然排序
        siftDownComparable(k, x);
}

private void siftDownUsingComparator(int k, E x) {
        int half = size >>> 1;
        while (k < half) {
        	//擷取小根堆的左孩子節點下标
            int child = (k << 1) + 1;
            Object c = queue[child];
            //擷取小根堆的右孩子節點下标
            int right = child + 1;
            if (right < size &&
                comparator.compare((E) c, (E) queue[right]) > 0)
                //找到左右孩子中較小的，記錄到c，用child記錄其下标
                c = queue[child = right];
             //利用下沉操作，直到平衡
            if (comparator.compare(x, (E) c) <= 0)
                break;
            queue[k] = c;
            //一直執行下沉操作
            k = child;
        }
        queue[k] = x;
}
private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        int half = size >>> 1;        // loop while a non-leaf
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is least
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
}

（7）indexOf(Object o)

//擷取元素o的下标值，時間複雜度為O（n）
private int indexOf(Object o) {
    if (o != null) {
        for (int i = 0; i < size; i++)
            if (o.equals(queue[i]))
                return i;
    }
    return -1;
}

（8）contains(Object o)

public boolean contains(Object o) {
	//判斷元素是否存在，調用公共方法indexOf
    return indexOf(o) != -1;
}

PriorityQueue優先隊列源碼解析QueuePriorityQueue

PriorityQueue

Queue

PriorityQueue

1.PriorityQueue簡介

2.基本屬性

3.基本方法

（1）add(E e)和offer(E e)

（2）grow(int minCapacity)擴容

（3）siftUp(int k, E x) 上浮調整函數

（4）peek()

（5）remove(Object o)和poll()

（6）siftDown(int k, E x)

繼續閱讀

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method

hdu7108哈希