<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    隨筆-13  評(píng)論-22  文章-0  trackbacks-0


    PriorityQueue

    本文github地址

    總體介紹

    前面以Java ArrayDeque為例講解了StackQueue,其實(shí)還有一種特殊的隊(duì)列叫做PriorityQueue,即優(yōu)先隊(duì)列。優(yōu)先隊(duì)列的作用是能保證每次取出的元素都是隊(duì)列中權(quán)值最小的(Java的優(yōu)先隊(duì)列每次取最小元素,C++的優(yōu)先隊(duì)列每次取最大元素)。這里牽涉到了大小關(guān)系,元素大小的評(píng)判可以通過元素本身的自然順序(natural ordering),也可以通過構(gòu)造時(shí)傳入的比較器Comparator,類似于C++的仿函數(shù))。

    Java中PriorityQueue實(shí)現(xiàn)了Queue接口,不允許放入null元素;其通過堆實(shí)現(xiàn),具體說是通過完全二叉樹(complete binary tree)實(shí)現(xiàn)的小頂堆(任意一個(gè)非葉子節(jié)點(diǎn)的權(quán)值,都不大于其左右子節(jié)點(diǎn)的權(quán)值),也就意味著可以通過數(shù)組來作為PriorityQueue的底層實(shí)現(xiàn)。

    PriorityQueue_base.png

    上圖中我們給每個(gè)元素按照層序遍歷的方式進(jìn)行了編號(hào),如果你足夠細(xì)心,會(huì)發(fā)現(xiàn)父節(jié)點(diǎn)和子節(jié)點(diǎn)的編號(hào)是有聯(lián)系的,更確切的說父子節(jié)點(diǎn)的編號(hào)之間有如下關(guān)系:

    leftNo = parentNo*2+1

    rightNo = parentNo*2+2

    parentNo = (nodeNo-1)/2

    通過上述三個(gè)公式,可以輕易計(jì)算出某個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)以及子節(jié)點(diǎn)的下標(biāo)。這也就是為什么可以直接用數(shù)組來存儲(chǔ)堆的原因。

    PriorityQueuepeek()element操作是常數(shù)時(shí)間,add(), offer(), 無參數(shù)的remove()以及poll()方法的時(shí)間復(fù)雜度都是log(N)

    方法剖析

    add()和offer()

    add(E e)offer(E e)的語義相同,都是向優(yōu)先隊(duì)列中插入元素,只是Queue接口規(guī)定二者對(duì)插入失敗時(shí)的處理不同,前者在插入失敗時(shí)拋出異常,后則則會(huì)返回false。對(duì)于PriorityQueue這兩個(gè)方法其實(shí)沒什么差別。

    PriorityQueue_offer.png

    新加入的元素可能會(huì)破壞小頂堆的性質(zhì),因此需要進(jìn)行必要的調(diào)整。

    //offer(E e)
    public boolean offer(E e) {
        if (e == null)//不允許放入null元素
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);//自動(dòng)擴(kuò)容
        size = i + 1;
        if (i == 0)//隊(duì)列原來為空,這是插入的第一個(gè)元素
            queue[0] = e;
        else
            siftUp(i, e);//調(diào)整
        return true;
    }
    上述代碼中,擴(kuò)容函數(shù)grow()類似于ArrayList里的grow()函數(shù),就是再申請(qǐng)一個(gè)更大的數(shù)組,并將原數(shù)組的元素復(fù)制過去,這里不再贅述。需要注意的是siftUp(int k, E x)方法,該方法用于插入元素x并維持堆的特性。
    //siftUp()
    private void siftUp(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)//調(diào)用比較器的比較方法
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }
    新加入的元素x可能會(huì)破壞小頂堆的性質(zhì),因此需要進(jìn)行調(diào)整。調(diào)整的過程為:k指定的位置開始,將x逐層與當(dāng)前點(diǎn)的parent進(jìn)行比較并交換,直到滿足x >= queue[parent]為止。注意這里的比較可以是元素的自然順序,也可以是依靠比較器的順序。

    element()和peek()

    element()peek()的語義完全相同,都是獲取但不刪除隊(duì)首元素,也就是隊(duì)列中權(quán)值最小的那個(gè)元素,二者唯一的區(qū)別是當(dāng)方法失敗時(shí)前者拋出異常,后者返回null。根據(jù)小頂堆的性質(zhì),堆頂那個(gè)元素就是全局最小的那個(gè);由于堆用數(shù)組表示,根據(jù)下標(biāo)關(guān)系,0下標(biāo)處的那個(gè)元素既是堆頂元素。所以直接返回?cái)?shù)組0下標(biāo)處的那個(gè)元素即可

    PriorityQueue_peek.png

    代碼也就非常簡(jiǎn)潔:

    //peek()
    public E peek() {
        if (size == 0)
            return null;
        return (E) queue[0];//0下標(biāo)處的那個(gè)元素就是最小的那個(gè)
    }

    remove()和poll()

    remove()poll()方法的語義也完全相同,都是獲取并刪除隊(duì)首元素,區(qū)別是當(dāng)方法失敗時(shí)前者拋出異常,后者返回null。由于刪除操作會(huì)改變隊(duì)列的結(jié)構(gòu),為維護(hù)小頂堆的性質(zhì),需要進(jìn)行必要的調(diào)整。

    PriorityQueue_poll.png
    代碼如下:

    public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];//0下標(biāo)處的那個(gè)元素就是最小的那個(gè)
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);//調(diào)整
        return result;
    }
    上述代碼首先記錄0下標(biāo)處的元素,并用最后一個(gè)元素替換0下標(biāo)位置的元素,之后調(diào)用siftDown()方法對(duì)堆進(jìn)行調(diào)整,最后返回原來0下標(biāo)處的那個(gè)元素(也就是最小的那個(gè)元素)。重點(diǎn)是siftDown(int k, E x)方法,該方法的作用是k指定的位置開始,將x逐層向下與當(dāng)前點(diǎn)的左右孩子中較小的那個(gè)交換,直到x小于或等于左右孩子中的任何一個(gè)為止
    //siftDown()
    private void siftDown(int k, E x) {
        int half = size >>> 1;
        while (k < half) {
            //首先找到左右孩子中較小的那個(gè),記錄到c里,并用child記錄其下標(biāo)
            int child = (k << 1) + 1;//leftNo = parentNo*2+1
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                comparator.compare((E) c, (E) queue[right]) > 0)
                c = queue[child = right];
            if (comparator.compare(x, (E) c) <= 0)
                break;
            queue[k] = c;//然后用c取代原來的值
            k = child;
        }
        queue[k] = x;
    }

    remove(Object o)

    remove(Object o)方法用于刪除隊(duì)列中跟o相等的某一個(gè)元素(如果有多個(gè)相等,只刪除一個(gè)),該方法不是Queue接口內(nèi)的方法,而是Collection接口的方法。由于刪除操作會(huì)改變隊(duì)列結(jié)構(gòu),所以要進(jìn)行調(diào)整;又由于刪除元素的位置可能是任意的,所以調(diào)整過程比其它函數(shù)稍加繁瑣。具體來說,remove(Object o)可以分為2種情況:1. 刪除的是最后一個(gè)元素。直接刪除即可,不需要調(diào)整。2. 刪除的不是最后一個(gè)元素。此處不再贅述。

    PriorityQueue_remove2.png

    具體代碼如下:

    //remove(Object o)
    public boolean remove(Object o) {
        //通過遍歷數(shù)組的方式找到第一個(gè)滿足o.equals(queue[i])元素的下標(biāo)
        int i = indexOf(o);
        if (i == -1)
            return false;
        int s = --size;
        if (s == i) //情況1
            queue[i] = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;
            siftDown(i, moved);//情況2
            
        }
        return true;
    }

    posted on 2016-05-12 21:22 CarpenterLee 閱讀(1447) 評(píng)論(2)  編輯  收藏

    評(píng)論:
    # re: Java PriorityQueue源碼剖析 2016-05-15 18:36 | 有機(jī)綠茶
    剖析得很詳細(xì),尤其是那些圖片,很形象,學(xué)習(xí)啦!  回復(fù)  更多評(píng)論
      
    # re: Java PriorityQueue源碼剖析 2016-05-16 07:27 | CarpenterLee
    @有機(jī)綠茶
    只有代碼太枯燥了,附圖更生動(dòng)些。  回復(fù)  更多評(píng)論
      

    只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


    網(wǎng)站導(dǎo)航:
     
    主站蜘蛛池模板: 又黄又爽一线毛片免费观看| 日韩亚洲人成在线综合日本| 毛片在线免费视频| mm1313亚洲国产精品无码试看| 亚洲 小说区 图片区 都市| 99视频在线免费观看| 久久99亚洲网美利坚合众国| 国产男女猛烈无遮挡免费视频| 两性色午夜视频免费网| 亚洲人成电影在线观看网| 最新精品亚洲成a人在线观看| 成人免费激情视频| h视频在线免费观看| 亚洲日韩国产精品乱-久| av无码免费一区二区三区| 免费精品久久久久久中文字幕| 亚洲尹人九九大色香蕉网站| 免费在线观看日韩| 69av免费视频| a毛看片免费观看视频| 久久精品国产亚洲av瑜伽| 久久精品亚洲精品国产色婷 | 亚洲精品美女久久7777777| 国产成A人亚洲精V品无码| 国产人成免费视频| 16女性下面无遮挡免费| 一个人免费观看视频在线中文 | 久久国产乱子伦精品免费午夜 | 麻豆一区二区三区蜜桃免费| 亚洲免费视频播放| 亚洲高清在线观看| 亚洲日韩在线观看| a级毛片在线视频免费观看| 亚洲aⅴ无码专区在线观看春色| 亚洲色四在线视频观看| 久久影视综合亚洲| 国产zzjjzzjj视频全免费| AA免费观看的1000部电影| 在线美女免费观看网站h| 两个人看的www视频免费完整版| 老司机亚洲精品影院在线观看|