數(shù)據(jù)結(jié)構(gòu)與算法（五），優(yōu)先隊(duì)列

這節(jié)總結(jié)一下優(yōu)先隊(duì)列的常用實(shí)現(xiàn)方法。

目錄：

  • 1、基本概念

  • 2、基于數(shù)組實(shí)現(xiàn)的優(yōu)先隊(duì)列

  • 2.1、基于有序數(shù)組的實(shí)現(xiàn)

  • 2.2、基于無序數(shù)組的實(shí)現(xiàn)

  • 3、基于堆實(shí)現(xiàn)的優(yōu)先隊(duì)列

  • 3.1、堆的有序化

  • 3.2、基于堆實(shí)現(xiàn)的優(yōu)先隊(duì)列

  • 4、索引優(yōu)先隊(duì)列

1、基本概念

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

抽象數(shù)據(jù)類型：

優(yōu)先隊(duì)列的接口同前面講到的隊(duì)列的接口一樣，是其基于泛型的API接口代碼如下：

public interface Queue<E> {

    //隊(duì)列是否為空
    boolean isEmpty();

    //隊(duì)列的大小
    int size();

    //入隊(duì)
    void enQueue(E element);

    //出隊(duì)
    E deQueue();
}

2、基于數(shù)組實(shí)現(xiàn)的優(yōu)先隊(duì)列

實(shí)現(xiàn)優(yōu)先隊(duì)列最簡(jiǎn)的方法就是基于前面講到的基于數(shù)組的棧的代碼，只需對(duì)插入或刪除操作作相應(yīng)的更改即可。

2.1、基于有序數(shù)組的實(shí)現(xiàn)

在棧的代碼的插入方法中添加代碼，將所有較大的元素向右移動(dòng)一格，以保證數(shù)組有序（和插入排序相同），這里我們可以使用二分查找的方法來找出元素應(yīng)插入的位置，然后再移動(dòng)元素。這樣最大元素，總是在數(shù)組的最右邊，其刪除操作和棧的實(shí)現(xiàn)中一樣。

代碼：

/**
 * 基于有序數(shù)組的實(shí)現(xiàn)的優(yōu)先隊(duì)列
 * @author Alent
 * @param <E>
 */
public class PriorityQueue<E extends Comparable<E>> implements Queue<E>{
    private E[] elements;
    private int size=0;
    
    @SuppressWarnings("unchecked")
    public PriorityQueue() {
        elements = (E[])new Comparable[1]; 
    }
    
    @Override public int size() {return size;}

    @Override public boolean isEmpty() {return size == 0;}

    @Override
    public void enQueue(E element) {
        if(size == elements.length) {
            resizingArray(2*size);//若數(shù)組已滿將長(zhǎng)度加倍
        }
        elements[size++] = element;
        insertSort(elements);
    }

    @Override
    public E deQueue() {
        E element = elements[--size];
        elements[size] = null;     //注意：避免對(duì)象游離
        if(size > 0 && size == elements.length/4) {
            resizingArray(elements.length/2);//小于數(shù)組1/4,將數(shù)組減半
        }
        return element;
    }
    
    //插入排序，由于前面n-1個(gè)元素是有序的，這里只插入最后一個(gè)元素
    public void insertSort(E[] a) {
        int N = size -1; //最后一個(gè)元素是size-1，不是a.length-1
        if(N == 0) return;
        int num = binaryFind(a, a[N], 0, N-1);
        E temp = a[N];
        //num后的元素向后移動(dòng)
        for (int j = N; j > num; j--) {
           a[j] = a[j-1];
        }
        a[num] = temp;
    }

    //找出元素應(yīng)在數(shù)組中插入的位置
    public int binaryFind(E[] a, E temp, int down, int up) {
        if(up<down || up>a.length || down<0) {
            System.out.println("下標(biāo)錯(cuò)誤");
        }
        if(temp.compareTo(a[down]) < 0) return down;
        if(temp.compareTo(a[up]) > 0) return up+1;
        int mid = (up-down)/2 + down;
        if(temp.compareTo(a[mid]) == 0) {
            return mid + 1;
        }else if(temp.compareTo(a[mid])<0) {
            up = mid-1;
        }else if(temp.compareTo(a[mid])>0) {
            down = mid+1;
        }
        return binaryFind(a,temp,down,up);
    }

    //交換兩個(gè)元素
    public void swap(E[] a,int i,int j) {
        E temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    //調(diào)整數(shù)組大小
    public void resizingArray(int num) {
        @SuppressWarnings("unchecked")
        E[] temp = (E[])new Comparable[num];
        for(int i=0;i<size;i++) {
            temp[i] = elements[i];
        }
        elements = temp;
    }
    
    public static void main(String[] args) {
        int[] a = {4,2,1,3,8,new Integer(5),7,6};//測(cè)試數(shù)組
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        System.out.print("入棧順序：");
        for(int i=0;i<a.length;i++) {
            System.out.print(a[i]+" ");
            pq.enQueue(a[i]);
        }
        System.out.println();
        System.out.print("出棧順序數(shù)組實(shí)現(xiàn)：");
        while(!pq.isEmpty()) {
            System.out.println(pq.deQueue());
        }
    }
}

2.2、基于無序數(shù)組的實(shí)現(xiàn)

同樣，我們一個(gè)可以在刪除方法中修改，在刪除方法中添加一段類似于選擇排序內(nèi)循環(huán)的代碼，每次刪除時(shí)先找出數(shù)組中的最大元素，然后與最右邊元素進(jìn)行交換，然后在刪除元素。

代碼：

@Override
public void enQueue(E element) {
    if(size == elements.length) {
        resizingArray(2*size);//若數(shù)組已滿將長(zhǎng)度加倍
    }
    elements[size++] = element;
}

@Override
public E deQueue() {
    swapMax(elements);
    E element = elements[--size];
    elements[size] = null;     //注意：避免對(duì)象游離
    if(size > 0 && size == elements.length/4) {
        resizingArray(elements.length/2);//小于數(shù)組1/4,將數(shù)組減半
    }
    return element;
}

public void swapMax(E[] a) {
    int max = size -1;
    for(int i=0;i<size-1; i++) {
        if(larger(a[i],a[max])) 
            max = i;
    }
    swap(a, size-1, max);
}

//比較兩個(gè)元素大小
public boolean larger(E a1, E a2) {
    return a1.compareTo(a2)>0;
}

3、基于堆實(shí)現(xiàn)的優(yōu)先隊(duì)列

基本概念：

當(dāng)一個(gè)二叉樹的每個(gè)結(jié)點(diǎn)都大于等于它的兩個(gè)子結(jié)點(diǎn)時(shí)，我們稱它是堆有序的。根結(jié)點(diǎn)是堆有序的二叉樹的最大結(jié)點(diǎn)。

二叉堆是一組能夠用堆有序的完全二叉樹排序的元素，并在數(shù)組中按照層級(jí)存儲(chǔ)。

一棵堆有序的完全二叉樹：


堆有序的完全二叉樹

為了操作方便，這是我們使用一個(gè)數(shù)組，來表示一個(gè)堆。我們不使用數(shù)組的第一個(gè)元素，具體實(shí)現(xiàn)在《數(shù)據(jù)結(jié)構(gòu)與算法（四），樹》中有提及，這里就不說了。

3.1、堆的有序化

當(dāng)我們將元素插入到堆（數(shù)組的末尾）中時(shí)，插入的元素可能比它的父結(jié)點(diǎn)要大，堆的有序狀態(tài)被打破。我們需要交換它和它的父節(jié)點(diǎn)來修堆，直到堆重新變?yōu)橛行驙顟B(tài)。其操作如下圖：

堆的插入操作

代碼如下：

//上浮操作
private void swim(int k) {
        while(k > 1 && less(k/2, k)) {
            swap(k/2, k);
            k = k/2;
        }
    }

private boolean less(int i, int j) {
    return elements[i].compareTo(elements[j]) < 0;
}

//交換兩個(gè)元素
public void swap(int i,int j) {
    E temp = elements[i];
    elements[i] = elements[j];
    elements[j] = temp;
}

同樣的，當(dāng)我們從堆中刪除根結(jié)點(diǎn)并將它的最后一個(gè)元素放到頂端時(shí)，堆的有序性被打破，我們需要將它與它的兩個(gè)子結(jié)點(diǎn)種的較大者進(jìn)行交換，以恢復(fù)堆的有序性，其操作流程如下圖：

堆的刪除操作

其代碼如下：

//下沉操作
private void sink(int k) {
    while(2*k <= size) {
        int j = 2*k;
        if(j < size && less(j, j+1))
            j++;
        if(!less(k,j))
            break;
        swap(k,j);
        k = j;
    }
}

3.2、基于堆實(shí)現(xiàn)的優(yōu)先隊(duì)列

基于堆的優(yōu)先隊(duì)列的實(shí)現(xiàn)代碼如下：

/**
 * 基于堆的優(yōu)先隊(duì)列
 * @author Alent
 */
public class MaxPQ<E extends Comparable<E>> implements Queue<E>{
    private E[] elements;
    private int size=0;
    
    @SuppressWarnings("unchecked")
    public MaxPQ(int capacity) {
        elements = (E[])new Comparable[capacity + 1]; 
    }
    
    @Override public int size() {return size;}

    @Override public boolean isEmpty() {return size == 0;}

    @Override
    public void enQueue(E element) {
        elements[++size] = element;
        swim(size);
    }
    
    //上浮
    private void swim(int k) {
        while(k > 1 && less(k/2, k)) {
            swap(k/2, k);
            k = k/2;
        }
    }
    
    private boolean less(int i, int j) {
        return elements[i].compareTo(elements[j]) < 0;
    }

    @Override
    public E deQueue() {
        E result = elements[1];
        swap(1, size--);
        elements[size + 1] = null;
        sink(1);
        return result;
    }
    
    //下沉
    private void sink(int k) {
        while(2*k <= size) {
            int j = 2*k;
            if(j < size && less(j, j+1))
                j++;
            if(!less(k,j))
                break;
            swap(k,j);
            k = j;
        }
    }

    //交換兩個(gè)元素
    public void swap(int i,int j) {
        E temp = elements[i];
        elements[i] = elements[j];
        elements[j] = temp;
    }
}

三種實(shí)現(xiàn)方法的時(shí)間復(fù)雜度比較：

4、索引優(yōu)先隊(duì)列

索引優(yōu)先隊(duì)列，它用一個(gè)索引數(shù)組保存了某個(gè)元素在優(yōu)先隊(duì)列中的位置，使得我們能夠引用已經(jīng)進(jìn)入優(yōu)先隊(duì)列中的元素。最在些應(yīng)用中，通常是很有必要的，如：有向圖的Dijkstra算法中就使用了索引優(yōu)先隊(duì)列，來返回最小邊的索引。

其實(shí)現(xiàn)方法為：

使用elements[]數(shù)組來保存隊(duì)列中的元素，pq[]數(shù)組用來保存elements中元素的索引，在添加一個(gè)數(shù)組qp[]來保存pq[]的逆序——qp[i]的值是i在pq[]中的位置（即 pq[qp[i]] = i）。若i不在隊(duì)列中，則令qp[i] = -1。輔助函數(shù)less()、swap()、sink()、swim()和前面優(yōu)先隊(duì)列中的一樣。

索引優(yōu)先隊(duì)列的代碼實(shí)現(xiàn)：

/**
 * 基于堆實(shí)現(xiàn)的索引優(yōu)先隊(duì)列
 */
public class IndexMinPQ<E extends Comparable<E>>{

    private int[] pq; //索引二叉堆
    private int[] qp; // 保存逆序：pq[qp[i]] = i;
    private E[] elements; //元素
    private int size = 0;

    @SuppressWarnings("unchecked")
    public IndexMinPQ(int capacity) {
        elements = (E[]) new Comparable[capacity + 1];
        pq = new int[capacity + 1];
        qp = new int[capacity + 1];
        for (int i = 0; i <= capacity; i++) {
            qp[i] = -1;
        }
    }

    public boolean isEmpty() {
        return size == 0;
    }
    //刪除最小元素，并返回索引
    public int delMin() {
        int index = pq[1];
        swap(1, size--);
        sink(1);
        elements[pq[size + 1]] = null;
        qp[pq[size + 1]] = -1;
        return index;
    }
    //刪除索引k及其元素
    public void delete(int k) {
        int index = qp[k];
        swap(index, size--);
        swim(index);
        sink(index);
        elements[k] = null;
        qp[k] = -1;
    }
    
    //插入元素，將它和索引k關(guān)聯(lián)
    public void insert(int k, E element) {
        size++;
        qp[k] = size;
        pq[size] = k;
        elements[k] = element;
        swim(size);
    }

     //改變索引k關(guān)聯(lián)的元素
    public void change(int k, E element) {
        elements[k] = element;
        swim(qp[k]);
        sink(qp[k]);
    }
    
    //是否包含索引k
    public boolean contains(int k) {
        return qp[k] != -1;
    }
    
    //下沉
    private void sink(int k) {
        while (2 * k <= size) {
            int j = 2 * k;
            if (j < size && less(j, j + 1))
                j++;
            if (!less(k, j))
                break;
            swap(k, j);
            k = j;
        }
    }

    //上浮
    private void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            swap(k, k / 2);
            k = k / 2;
        }
    }
    private boolean less(int i, int j) {
        return elements[pq[i]].compareTo(elements[pq[j]]) > 0;
    }

    //交換兩元素
    private void swap(int i, int j) {
        int swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }
}

索引優(yōu)先隊(duì)列的時(shí)間復(fù)雜度：

索引優(yōu)先隊(duì)列的時(shí)間復(fù)雜度

找出最大元素的索引優(yōu)先隊(duì)列的JAVA版本IndexMaxPQ.java 點(diǎn)這里。

好了，這節(jié)就總結(jié)這么多吧。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容