java集合（十）---Queue與PriorityQueue、Deque源碼解析

一、Queue與PriorityQueue、Deque的圖如下所示：

（1）從上圖可以看出，Queue接口有兩個實作類：PriorityQueue與Deque

（2）ArrayDeque是Deque的一個典型的實作類

二、Queue：

Queue是什麼？

（1）Queue是具有隊列特性的接口

（2）Queue具有“先進先出（FIFO）”的特性

（3）Queue所有新元素都插入隊列的末尾，移除元素都移除隊列的頭部

（4）注意：隊列不允許随機通路隊列中的元素

（5）Queue接口中定義了如下幾個方法：

三、Deque：

Deque是什麼？

（1）Deque是一個雙端隊列

（2）Deque繼承自Queue

（3）Deque具有先進先出或後進先出的特點

（4）Deque支援所有元素在頭部和尾部進行插入、删除、擷取

（5）Deque中定義了如下幾個方法：

從上面可以看出，Deque不僅可以當成雙端隊列使用，而且可以被當成棧來使用，因為該類包含了pop、push兩個方法。

ArrayDeque：

Deque接口提供了一個典型的實作類：ArrayDeque。

從該名稱可以看出，它是一個基于數組實作的雙端隊列，建立Deque時同樣可以指定numElements參數，該參數用于指定Object[]數組的長度，如果不指定numElements參數，Deque底層數組長度為16.

public class ArrayDeque<E> extends AbstractCollection<E>
                       implements Deque<E>, Cloneable, Serializable{}

           

下面分别舉一下例子：

addAll©：

public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
        //将元素全部加到ArrayDeque中。其中add 方法調用了addLast 後面會對addLast源碼進行分析
    }

public boolean add(E e) {
        addLast(e);
        return true;
    }  

           

addFirst：

public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        //如果加入的元素為null 抛出空指針異常。    
        elements[head = (head - 1) & (elements.length - 1)] = e;
        //head值先減1，然後将元素放到head位置
        if (head == tail)
            doubleCapacity();
            //如果head == tail 将數組大小擴大一倍
    }

           

相應解釋：

①addFirst 加一個元素時，head都會先減1，然後再放元素。head初始值為 0。

② (head - 1) & (elements.length - 1) 使head的值在【0， elements.length - 1】範圍之内，同時可以循環利用數組裡面的空間，head一直圍着數組轉圈。

③如果tail==head 的時候，由上圖可知數組中的元素已經滿了，是以會将數組的擴大一倍。初始時tail=0

addLast：

public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        //将e的值放到tail位置，然後tail+1，如果數組滿了擴容一倍。
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

           

addLast 時操作 tail 在tail位置加入元素，如果數組已經滿了就擴容一倍

pollFirst：

public E pollFirst() {
        int h = head;
        E result = elements[h]; //将elements[h]指派給result。
        if (result == null)
            return null;//如果result 為null 直接傳回
        elements[h] = null;     // 如果result不為null 将elements[h] 指派為null
        head = (h + 1) & (elements.length - 1);// head+1.
        return result;
    }
           

下面是一個使用pollFirst的例子：

public class DequeDemo {
    public static void main(String[] args) {
        Integer []arr={1,2,3,4,5,6,7,8};
        List<Integer> list=Arrays.asList(arr);
         ArrayDeque<Integer> aDeque=new ArrayDeque<Integer>(list);
         for(int i=0;i<3;i++)
             aDeque.addFirst(arr[i]);
             //往雙端隊列中添加元素
         while(!aDeque.isEmpty())
            aDeque.pollFirst();
        //使用pollFirst()删除。
    }

}
           

pollLast：

public E pollLast() {
        int t = (tail - 1) & (elements.length - 1);
        E result = elements[t];
        //tail 先減1然後擷取tail中的内容。
        if (result == null)
            return null;//如果result 為null 直接傳回
        elements[t] = null;//否則将t位置的元素清空再傳回result
        tail = t;
        return result;
    }
           

下面是一個使用pollLast的例子：

public class DequeDemo {
    public static void main(String[] args) {
        Integer []arr={1,2,3,4,5,6,7,8};
        List<Integer> list=Arrays.asList(arr);
         ArrayDeque<Integer> aDeque=new ArrayDeque<Integer>(list);
         for(int i=0;i<3;i++)
             aDeque.addFirst(arr[i]);
             //添加元素
         while(!aDeque.isEmpty())
            aDeque.pollLast();
        //删除元素
    }

}
           

removeFirst()：

public E removeFirst() {
        E x = pollFirst();
        //調用pollFirst()
        if (x == null)
            throw new NoSuchElementException();
            //當pollFirst()傳回null抛出null 元素異常。
        return x;
    }
           

由上面代碼可知其實removeFirst() 就是調用pollFirst() 不同之處在于在當pollFirst()傳回null removeFirst() 抛出 null 元素異常。

removeLast()：

public E removeLast() {
        E x = pollLast();
        //調用 pollLast() 當pollLast()傳回null抛出null 元素異常。
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }
           

由上面代碼可知其實removeLast() 就是調用pollLast() 不同之處在于在當pollLast()傳回null removeLast() 抛出 null 元素異常

add(E e)：

public boolean add(E e) {
 //調用 addLast(e); 添加成功傳回 true。
        addLast(e);
        return true;
    }

           

remove()：

public E remove() {
        return removeFirst();
    }
           

四、PriorityQueue：

（1）PriorityQueue是一個比較标準的隊列實作類。是因為：PriorityQueue儲存隊列元素的順序并不是按照加入隊列的順序，而是按照隊列元素的大小進行重新排列。

（2）PriorityQueue不允許插入null元素，它還需要對隊列元素進行排序。

（3）PriorityQueue有兩種排序方式：自然排序 和 定制排序。

（4）自然排序：其必須實作Comparable接口，而且應該是同一個類的多個執行個體，否則會導緻ClassCaseException異常

（5）定制排序：要傳入一個Comparator對象，該對象負責對隊列的所有元素進行排序，采用定制排序時不要求隊列元素實作Comparable接口

（6）PriorityQueue與TreeSet對元素的要求基本一緻，可以參考TreeSet。

（7）優先隊列PriorityQueue具有小根堆性質，該類在邏輯上是使用堆實作的，即完全二叉樹；該類在存儲記憶體時，是将其轉換為數組存儲的

（8）完全二叉樹是指：葉節點隻能出現在最下層和次下層，并且最下面一層的結點都集中在該層最左邊的若幹位置的二叉樹。下圖顯示一棵完全二叉樹和一棵非完全二叉樹。如下圖：（左邊是一顆完全二叉樹，右邊是一顆不完全二叉樹）

（9）PriorityQueue總是先輸出根節點的值，然後調整樹使之繼續成為一棵完全二叉樹，保證每次輸出的根節點總是整棵樹優先級最高的，要麼數值最小要麼數值最大

成員方法源碼解析：

1. public PriorityQueue()無參構造方法：

public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
           

源碼解析：

• 功能：建立一個初始容量為11(DEFAULT_INITIAL_CAPACITY)的PriorityQueue，其中隊列中元素的比較方式是按照自然排序的方式進行比較
• 源碼思路：
  • 調用該類的帶有兩個參數的構造方法實作建立對象

2. public PriorityQueue(int initialCapacity)方法

public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }
           

源碼解析：

• 功能：建立一個帶有初始容量的優先隊列，其中隊列中元素的比較方式是按照自然排序的方式進行比較
• 源碼思路：
  • 調用該類的帶有兩個參數的構造方法實作建立對象

3. public PriorityQueue(Comparator<? super E> comparator)方法

public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }
           

源碼解析：

• 功能：建立一個帶有比較器的優先隊列，其中隊列的容量為預設的初始容量DEFAULT_INITIAL_CAPACITY（11）
• 源碼思路：
  • 調用該類的帶有兩個參數的構造方法實作建立對象

4. public PriorityQueue(int initialCapacity,Comparator<? super E> 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;
    }
           

源碼解析：

• 功能：建立一個帶有比較器，帶有自定義隊列容量的優先隊列
• 源碼思路：
  • （1）首先判斷自定義隊列容量是否小于1，小于1時抛出異常
  • （2）給隊列的數組queue建立容量為initialCapacity的記憶體空間
  • （3）将比較器傳遞給目前對象

5. public PriorityQueue(Collection<? extends E> c)方法

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

源碼解析：

• 功能：建立一個優先隊列，隊列中包含集合c中的元素，如果集合c的類型是SortedSet或者是PriorityQueue類型，那麼建立的優先隊列中元素的比較方法按照集合c的比較方法進行比較，否則按照自然順序進行比較
• 源碼思路：
  • （1）判斷如果集合c屬于SortedSet類型，則将集合c強制轉換為SortedSet類型，将c的比較器指派給目前優先隊列對象的比較器，然後調用initElementsFromCollection()方法，建立優先隊列
  • （2）如果集合c不屬于SortedSet類型，而屬于PriorityQueue類型，則将集合c強制轉換為PriorityQueue類型，将c的比較器指派給目前優先隊列對象的比較器，然後調用initFromPriorityQueue（）方法，建立優先隊列
  • （3）如果（1）和（2）中的判斷條件都不滿足，則将目前優先隊列的比較器設定為空，調用initFromCollection（）方法，建立優先隊列

6. public PriorityQueue(PriorityQueue<? extends E> c)方法

@SuppressWarnings("unchecked")
    public PriorityQueue(PriorityQueue<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initFromPriorityQueue(c);
    }
           

源碼解析：

• 功能：建立一個優先隊列，隊列中包含優先隊列c中的元素
• 源碼思路：
  • （1）将c的比較器指派給目前隊列的比較器
  • （2）調用initFromPriorityQueue()方法，建立優先隊列

7. public PriorityQueue(SortedSet<? extends E> c)方法

@SuppressWarnings("unchecked")
    public PriorityQueue(SortedSet<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initElementsFromCollection(c);
    }
           

源碼解析：

• 功能：建立一個優先隊列，隊列中包含SortedSet類型對象c中的元素
• 源碼思路：
  • （1）将c的比較器指派給目前對象的比較器中
  • （2）調用initElementsFromCollection方法，建立優先隊列

8. private void initFromPriorityQueue(PriorityQueue<? extends E> c)方法

private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
        if (c.getClass() == PriorityQueue.class) {
            this.queue = c.toArray();
            this.size = c.size();
        } else {
            initFromCollection(c);
        }
    }
           

源碼解析：

• 功能：這是一個子方法，實作的功能是将優先隊列c中的數組和數組大小指派給目前優先隊列對象中
• 源碼思路：
  • （1）首先判斷c的類型是否是PriorityQueue類型，如果是則将優先隊列c中的數組和數組大小指派給目前優先隊列對象中
  • （2）如果c的類型不是PriorityQueue類型，則調用initFromCollection()方法

9. private void initElementsFromCollection(Collection<? extends E> c)方法

private void initElementsFromCollection(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if (a.getClass() != Object[].class)
            a = Arrays.copyOf(a, a.length, Object[].class);
        int len = a.length;
        if (len == 1 || this.comparator != null)
            for (int i = 0; i < len; i++)
                if (a[i] == null)
                    throw new NullPointerException();
        this.queue = a;
        this.size = a.length;
    }
           

源碼解析：

• 功能：将集合c中的數組值和數組大小傳遞給目前優先隊列對象中
• 源碼思路：
  • （1）首先定義個Object類型的數組a，将c中的元素轉換到數組a中
  • （2）判斷a集合的類型是否是Object類型的數組，如果不是，通過調用Arrays類的copyOf方法，将其轉換為Object類型的數組
  • （3）定義一個整型變量len，用于存儲數組a的長度
  • （4）如果數組長度為1或者疊代器不為null時，進行循環操作，循環的内容是：判斷數組中是否有null元素，如果有則抛出異常，如果所有元素都不為null，則執行（5）
  • （5）将數組a的值指派給目前優先隊列的queue，将數組的長度指派給目前優先隊列的size

10. private void initFromCollection(Collection<? extends E> c)方法

private void initFromCollection(Collection<? extends E> c) {
        initElementsFromCollection(c);
        heapify();
    }
           

源碼解析：

• 功能：将集合c中的元素指派給目前優先隊列
• 源碼思路：
  • （1）調用initElementsFromCollection()方法實作指派操作
  • （2）調用heapify()方法

11. private void grow(int minCapacity)方法

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

源碼解析：

• 功能：增加數組的容量
• 源碼思路：
  • （1）定義整型變量newCapacity，其值為優先隊列數組的長度
  • （2）如果長度小于64，則添加到原來的2倍，如果大于64，則增加為原來的一半
  • （3）如果新增加的數組容量大于整型的最大值-8，那麼需要調用hugeCapacity()方法修改數組容量
  • （4）最後将數組和新的容量傳回給目前隊列數組

12. private static int hugeCapacity(int minCapacity)方法

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
           

源碼解析：

• 功能：按照minCapacity對數組進行擴容
• 源碼思路：
  • （1）如果想要添加的容量值小于0，則抛出異常
  • （2）傳回minCapacity大于MAX_ARRAY_SIZE值，則傳回整型最大值，否則傳回MAX_ARRAY_SIZE值

13. public boolean add(E e)方法

public boolean add(E e) {
        return offer(e);
    }
           

源碼解析：

• 功能：向優先隊列中添加元素e
• 源碼思路：
  • 調用該類的offer()方法實作該操作

14. public boolean offer(E e)方法

public boolean offer(E e) {
        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] = e;
        else
            siftUp(i, e);
        return true;
    }
           

源碼解析：

• 功能：向優先隊列中添加元素e，添加元素的核心是***siftUp()***方法
• 源碼思路：
  • （1）首先判斷元素e是否為null，如果為null，則抛出異常，否則執行下述步驟
  • （2）因為向隊列中插入元素，修改了隊列的結構，是以modCount需要自加1
  • （3）定義變量i，用來隊列的size
  • （4）如果變量i的值大于隊列的數組長度，需要調用grow()方法，增加隊列數組的長度，對應的size值要+1
  • （5）如果i=0，說明隊列中沒有元素，那麼新插進來的元素就可以作為樹根，否則要調用siftUp()方法來實作小根堆的調整

15. public E peek()方法

public E peek() {
        return (size == 0) ? null : (E) queue[0];
    }
           

源碼解析：

• 功能：擷取隊列中的隊頭元素，即小根堆的根結點值
• 源碼思路：
  • 判斷如果size的值等于0，說明隊列中沒有元素，傳回null；否則傳回隊列的頭元素

16. private int indexOf(Object o)方法

private int indexOf(Object o) {
        if (o != null) {
            for (int i = 0; i < size; i++)
                if (o.equals(queue[i]))
                    return i;
        }
        return -1;
    }
           

源碼解析：

• 功能：查找隊列中元素值為o的結點的位置
• 源碼思路：
  • （1）首先判斷查找的元素是否為null，如果是null，因為隊列中不存儲null元素，是以傳回-1，否則執行（2）步驟
  • （2）通過for循環進行周遊，每次周遊都使用equals方法來比較目前的元素是否與o元素相等，如果相等，則傳回目前元素的位置

17. public boolean remove(Object o)方法

public boolean remove(Object o) {
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }
           

源碼解析：

• 功能：移除隊列中元素為o的結點
• 源碼思路：
  • （1）首先根據元素o調用indexOf()方法找到元素o的位置，将該位置存儲在變量i中
  • （2）判斷i的值是否為-1，-1表示隊列中不包含該元素，則傳回false
  • （3）如果隊列中包含該元素，則調用removeAt()方法，将該元素從隊列中移除

18. boolean removeEq(Object o)方法

boolean removeEq(Object o) {
        for (int i = 0; i < size; i++) {
            if (o == queue[i]) {
                removeAt(i);
                return true;
            }
        }
        return false;
    }
           

源碼解析：

• 功能：将元素o從隊列中移除
• 源碼思路：
  • 通過for循環周遊元素，使用==運算符判斷是否找到元素，找到後調用remove()方法将元素從隊列中移除

19. public boolean contains(Object o)方法

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

源碼解析：

• 功能：判斷隊列中是否包含元素o
• 源碼思路：
  • 調用indexOf()方法，如果有該元素，indexOf()方法會傳回元素的位置
  • 判斷元素位置是否為-1，如果為-1則說明不包含該元素，方法傳回false，否則傳回true

20. public Object[] toArray()方法

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

源碼解析：

• 功能：将隊列的元素轉換為數組
• 源碼思路：
  • 調用Arrays.copyOf()方法，将隊列中的數組和數組大小傳遞到方法中，傳回Object類型數組

21. public T[] toArray(T[] a)方法

public <T> T[] toArray(T[] a) {
        final int size = this.size;
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(queue, size, a.getClass());
        System.arraycopy(queue, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }
           

源碼解析：

• 功能：将隊列中的元素存儲在數組a中
• 源碼思路：
  • （1）首先定義一個final int類型的變量size，擷取目前隊列的size
  • （2）如果将傳回的數組大小小于目前隊列的size大小，則直接調用Arrays類的copyOf方法将隊列和隊列的大小，a的類型傳遞進去，傳回該隊列對應的數組。否則執行步驟（3）
  • （3）調用System類的arraycopy方法，将queue數組從0開始指派給數組a，指派的數組大小為size
  • （4）如果a數組的大小大于size，說明設定的初始将傳回的數組a大小太大，需要将多餘的部分的第一個元素設定為null

22. public Iterator iterator()方法

public Iterator<E> iterator() {
        return new Itr();
    }
           

源碼解析：

• 功能：建立優先隊列的疊代器

23. public int size()方法

public int size() {
        return size;
    }
           

源碼解析：

• 功能：傳回隊列的size元素個數

24. public void clear()方法

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

源碼解析：

• 功能：清除隊列中的所有元素
• 源碼思路：
  • （1）因為清除操作是對隊列的結構性修改，是以需要讓modCount自加1
  • （2）使用for循環周遊隊列，每次循環都将循環到的元素值置為null
  • （3）最後将size的值變為0

25. public E poll()方法

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

源碼解析：

• 功能：删除堆的根結點
• 源碼思路：
  • （1）首先判斷隊列中是否有元素，如果有元素，則傳回null
  • （2）定義變量s，其值等于隊列的size-1，同時将隊列的size值-1
  • （3）定義變量result，其值等于堆的根結點值，定義變量x，其值等于堆的最後一個元素的值
  • （4）将堆的最後一個元素值置為null，因為要删除根結點，是以滿足堆的定義，最後一個元素一定為null
  • （5）如果隊列的最後一個元素不是堆的第一個元素，就需要将堆的最後一個元素按照小根堆的規則找到它的新位置，是以調用siftDown()方法進行調整

26. private E removeAt(int i)方法

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

源碼解析：

• 功能：移除隊列中位置為i的元素
• 源碼思路：
  • （1）因為移除操作是對隊列的結構上的修改，是以需要modCount+1
  • （2）定義整型變量s，其值等于size-1,同時将隊列的size值-1
  • （3）如果要删除的元素是隊列的最後一個元素，則直接将最後一個元素置為null
  • （4）否則定義變量moved，用來存儲隊列中的最後一個元素
  • （5）因為要移除一個元素，是以隊列的最後一個元素要移動保證小根堆的性質，是以最後一個元素一定變為null，移動最後一個元素的規則是調用siftDown(i,moved)方法

27. private void siftUp(int k, E x)方法

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

源碼解析：

• 功能： 在k位置插入元素x
• 源碼思路：
  • （1）首先判斷疊代器是否為null，如果不為空調用siftUpUsingComparator(k, x)方法，保證隊列是小根堆
  • （2）如果疊代器尾null，調用siftUpComparable(k, x)方法

28. private void siftUpComparable(int k, E 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;
    }
           

源碼解析：

• 功能：向隊列中位置為k的地方插入元素x
• 源碼思路：
• （1）首先擷取元素x的比較器，将其放在Comparable類型的key變量中
• （2）循環，循環條件k>0。定義變量parent，其值等于位置為k的元素的父節點的位置
• （3）定義變量e，其值為 位置為k的元素的父節點的位置的變量
• （4）調用構造器判斷目前将插入的元素與插入位置的父節點的值大小，如果大于父節點的值，則滿足小根堆，直接跳出循環，将插入的元素x插入到位置k；否則，執行步驟（5）

• （5）将位置為k的元素值變為其父節點的值，将其父節點的值變為插入元素x的值

  下面示例：

  目前隊列中有如下元素[1, 2, 8, 9, 6]

  

  元素在邏輯上的存儲方式如上圖，現在想要再插入元素4，即如果執行add(4)方法，會出現的結果是

  

  該過程如果用siftUpComparable()方法來講解的話，過程如下：
• 首先k=5， parent = （5-1）/2 = 2，e = 10， 因為比較的結果是queue[parent] >queue[k]，是以将8放在位置5，k = 2;
• 目前k=2，parent = 0，e = 1，因為比較的結果是queue[parent]< queue[k]，是以不執行if裡面的語句，而執行queue[0] = 1，k = 0
• 因為 k =0，退出循環體
• 最後執行queue[2] = 4

29. private void siftUpUsingComparator(int k, E x)方法

private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }
           

源碼解析：

• 功能：向隊列中位置為k的地方插入元素x，與上一個方法的不同之處就是這個方法提供了自己的比較器，是以比較結點值大小的時候使用提供的比較器比較

30. private void siftDown(int k, E x)方法

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

源碼解析：

• 功能：從堆的第一個元素往下比較，如果比左右孩子節點的最小值小則與最小值交換，交換後繼續向下比較，否則停止比較

31. private void siftDownComparable(int k, E 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;
    }
           

感謝：

參考：https://blog.csdn.net/u013309870/article/details/71478120

https://blog.csdn.net/xiaojie_570/article/details/79915942