Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊列實例分析

本文小編為大家詳細(xì)介紹“Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊列實例分析”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊列實例分析”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識吧。

一、堆的概念

堆的定義：n個元素的序列{k1 , k2 , … , kn}稱之為堆，當(dāng)且僅當(dāng)滿足以下條件時：

（1）ki >= k2i 且 ki >= k(2i+1) ——大根堆

（2） ki <= k2i 且 ki <= k(2i+1) &mdash;&mdash;小根堆

簡單來說：

堆是具有以下性質(zhì)的完全二叉樹：
（1）每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值，稱為大根堆（如左下圖）；
或者：
（1）每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值，稱為小根堆（如右下圖）。

我們使用數(shù)組保存二叉樹結(jié)構(gòu)，即是將二叉樹用層序遍歷方式放入數(shù)組中，如上圖。

堆的元素下標(biāo)存在以下關(guān)系：

1.假如已知雙親（parent）的下標(biāo)，則

左孩子（left）下標(biāo) = 2parent + 1；

右孩子（right）下標(biāo) = 2parent +2；

2.已知孩子（child）（不區(qū)分左右）下標(biāo)，則：

雙親（parent）下標(biāo) = （child - 1）/ 2 ;

小結(jié)：

• 堆邏輯上是一棵完全二叉樹；

• 堆物理上保存在數(shù)組中；

• 滿足任意結(jié)點的值都大于其子樹中結(jié)點的值，叫做大堆，或者大根堆，或者最大堆；反之，則是小堆，或者小根堆，或者最小堆；

• 堆的基本作用是，快速找集合中的最值。

二、向下調(diào)整

1.建初堆

設(shè)有一個無序序列 {2,5,7,8,4,6,3,0,9,1 }，下面通過圖解來建初始堆。

這里有一個前提：這棵二叉樹的左右子樹都必須是一個堆，才能進(jìn)行調(diào)整。

下面是用到的數(shù)據(jù)的一些說明：

• array 代表存儲堆的數(shù)組

• size 代表數(shù)組中被視為堆數(shù)據(jù)的個數(shù)

• index 代表要調(diào)整位置的下標(biāo)

• left 代表 index 左孩子下標(biāo)

• right 代表 index 右孩子下標(biāo)

• min 代表 index 的最小值孩子的下標(biāo)

過程文字描述如下：

1.index 如果已經(jīng)是葉子結(jié)點，則整個調(diào)整過程結(jié)束：

（1）判斷 index 位置有沒有孩子；

（2） 因為堆是完全二叉樹，沒有左孩子就一定沒有右孩子，所以判斷是否有左孩子；

（3） 因為堆的存儲結(jié)構(gòu)是數(shù)組，所以判斷是否有左孩子即判斷左孩子下標(biāo)是否越界，即 left >= size 越界。

2.確定 left 或 right，誰是 index 的最小孩子 min：

（1） 如果右孩子不存在，則 min = left；

（2）否則，比較 array[left] 和 array[right] 值得大小，選擇小的為 min；

（3）比較 array[index] 的值 和 array[min] 的值，如果 array[index] <= array[min]，則滿足堆的性質(zhì)，調(diào)整結(jié)束。

3.否則，交換 array[index] 和 array[min] 的值；

4.然后因為 min 位置的堆的性質(zhì)可能被破壞，所以把 min 視作 index，向下重復(fù)以上過程。

通過上面的操作描述，我們寫出以下代碼：

public static void shiftDown(int[] array, int size, int index){
        int left = 2*index +1;
        while(left < size){
            int min = left;
            int right = 2*index +2;
            if(right<size){
                if(array[right] < array[left]){
                    min = right;
                }
            }
            if(array[index] <= array[min]){
                break;
            }
            int tmp = array[index];
            array[index] = array[min];
            array[min] = tmp;
            index = min;
            left = 2*index +1;
        }
    }

時間復(fù)雜度為 O(log(n))。

2.建堆

下面我們給出一個數(shù)組，這個數(shù)組邏輯上可以看做一顆完全二叉樹，但是還不是一個堆，現(xiàn)在我們通過算法，把它構(gòu)建成一個堆。根節(jié)點左右子樹不是堆，我們怎么調(diào)整呢？這里我們從倒數(shù)的第一個非葉子節(jié)點的子樹開始調(diào)整，一直調(diào)整到根節(jié)點的樹，就可以調(diào)整成堆。

時間復(fù)雜度分析：

粗略估算，可以認(rèn)為是在循環(huán)中執(zhí)行向下調(diào)整，為 O(n * log(n))，（了解）實際上是 O(n)。

//建堆代碼
    public void createHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
        //根據(jù)代碼 顯示的時間復(fù)雜度   看起來 應(yīng)該是O(n*logn)  但是 實際上是O(n)
        for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
            //調(diào)整
            shiftDown(parent,usedSize);
        }
    }

三、優(yōu)先級隊列

1.什么是優(yōu)先隊列？

根據(jù)百科解釋：

普通的隊列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，元素在隊列尾追加，而從隊列頭刪除。在優(yōu)先隊列中，元素被賦予優(yōu)先級。當(dāng)訪問元素時，具有最高優(yōu)先級的元素最先刪除。優(yōu)先隊列具有最高級先出（first in, largest out）的行為特征。通常采用堆數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。

所以我們在這里實現(xiàn)優(yōu)先隊列的內(nèi)部原理是堆，也就是說采用堆來構(gòu)建。

2.入隊列

過程（以大堆為例）：

• 首先按尾插方式放入數(shù)組；

• 比較其和其雙親的值的大小，如果雙親的值大，則滿足堆的性質(zhì)，插入結(jié)束；

• 否則，交換其和雙親位置的值，重新進(jìn)行 2、3 步驟；

• 直到根結(jié)點。

下面圖解：

    private void shiftUp(int child) {
        int parent = (child-1)/2;
        while (child > 0) {
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }

3.出隊列

為了防止破壞堆的結(jié)構(gòu)，刪除時并不是直接將堆頂元素刪除，而是用數(shù)組的最后一個元素替換堆頂元素，然后通過向 下調(diào)整方式重新調(diào)整成堆。

    private void shiftUp(int child) {
        int parent = (child-1)/2;
        while (child > 0) {
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }

    public void offer(int val) {
        if(isFull()) {
            //擴(kuò)容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
        //注意這里傳入的是usedSize-1
        shiftUp(usedSize-1);
    }

4.返回隊首元素

直接返回堆頂元素

    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException("優(yōu)先級隊列為空！");
        }
        return elem[0];
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

整體的代碼：

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    /**
     * 向下調(diào)整函數(shù)的實現(xiàn)
     * @param parent 每棵樹的根節(jié)點
     * @param len 每棵樹的調(diào)整的結(jié)束位置  10
     */
    public void shiftDown(int parent,int len) {
        int child = 2*parent+1;
        //1、最起碼 是有左孩子的，至少有1個孩子
        while (child < len) {
            if(child+1 < len && elem[child] < elem[child+1]) {
                child++;//保證當(dāng)前左右孩子最大值的下標(biāo)
            }
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    public void createHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
        //根據(jù)代碼 顯示的時間復(fù)雜度   看起來 應(yīng)該是O(n*logn)  但是 實際上是O(n)
        for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
            //調(diào)整
            shiftDown(parent,usedSize);
        }
    }

    private void shiftUp(int child) {
        int parent = (child-1)/2;
        while (child > 0) {
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }

    public void offer(int val) {
        if(isFull()) {
            //擴(kuò)容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
        //注意這里傳入的是usedSize-1
        shiftUp(usedSize-1);
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    public int poll() {
        if(isEmpty()) {
            throw new RuntimeException("優(yōu)先級隊列為空！");
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;
        shiftDown(0,usedSize);
        return tmp;
    }


    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException("優(yōu)先級隊列為空！");
        }
        return elem[0];
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }


    public void heapSort() {
        int end = this.usedSize-1;
        while (end > 0) {
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;
            shiftDown(0,end);
            end--;
        }
    }

}

5.堆的其他TopK問題

什么是TopK問題？

從arr[1, n]這n個數(shù)中，找出最大的k個數(shù)，這就是經(jīng)典的TopK問題。

解決這類問題，我們往往會有以下幾種思路：

• 對整體進(jìn)行排序，輸出前10個最大的元素。

• 用上面剛剛講的堆。

• 也是用堆，不過這比第二個思路更巧妙。

我們直接講思路三：

1. 先用前k個元素生成一個小頂堆，這個小頂堆用于存儲，當(dāng)前最大的k個元素。

2. 接著，從第k+1個元素開始掃描，和堆頂（堆中最小的元素）比較，如果被掃描的元素大于堆頂，則替換堆頂?shù)脑兀⒄{(diào)整堆，以保證堆內(nèi)的k個元素，總是當(dāng)前最大的k個元素。

3. 直到，掃描完所有n-k個元素，最終堆中的k個元素，就是所要求的TopK。

以這個數(shù)組{12，15，21，41，30}為例，找到前3個最大的元素。

那如果是將一組進(jìn)行從小到大排序，我們該采用大根堆還是小根堆？

答案是：大根堆！

步驟如下：

• 將這組數(shù)據(jù)調(diào)整為大根堆調(diào)整為大根堆；

• 0下標(biāo)和最后1個未排序的元素進(jìn)行交換即可；

• 重復(fù)1、2，直到結(jié)束。

總結(jié)：

如果求前K個最大的元素，要建一個小根堆。如果求前K個最小的元素，要建一個大根堆。第K大的元素。建一個小堆，堆頂元素就是第K大的元素。第K小的元素。建一個大堆，堆頂元素就是第K小的元素。

    public void heapSort() {
        int end = this.usedSize-1;
        while (end > 0) {
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;
            shiftDown(0,end);
            end--;
        }
    }
    public void shiftDown(int parent,int len) {
        int child = 2*parent+1;
        //1、最起碼 是有左孩子的，至少有1個孩子
        while (child < len) {
            if(child+1 < len && elem[child] < elem[child+1]) {
                child++;//保證當(dāng)前左右孩子最大值的下標(biāo)
            }
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

讀到這里，這篇“Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊列實例分析”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領(lǐng)會，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。