??博客主頁(yè)：?【小扳_-CSDN博客】
?感謝大家點(diǎn)贊??收藏?評(píng)論???

文章目錄

? ? ? ? 1.0 優(yōu)先級(jí)隊(duì)列說(shuō)明

? ? ? ? 2.0 用數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列

? ? ? ? 3.0?無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列

? ? ? ? 3.1 無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 入隊(duì)列 offer(E value)

? ? ? ? 3.2 無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 出隊(duì)列 poll()

? ? ? ? 3.3?無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 查看隊(duì)列中優(yōu)先級(jí)最大的元素 peek()?

? ? ? ? 3.4 無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 判斷是否為空隊(duì)列

? ? ? ? 3.5 無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 判斷是否為滿隊(duì)列

????????3.6?無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列完整代碼

? ? ? ? 4.0 有序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列

? ? ? ? 4.1 有序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 入隊(duì)列 offer(E value)

? ? ? ? 4.2 有序數(shù)組實(shí)現(xiàn)有序隊(duì)列 - 出隊(duì)列 poll()

? ? ? ? 4.3?有序數(shù)組實(shí)現(xiàn)有序隊(duì)列 - 查看優(yōu)先級(jí)最大的元素 peek()

? ? ? ? 4.4 有序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 判斷隊(duì)列是否為空

? ? ? ? 4.5 有序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 判斷隊(duì)列是否為滿隊(duì)列

? ? ? ? 4.6 有序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列完整代碼

? ? ? ? 5.0 大頂堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列

? ? ? ? 5.1 堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 入隊(duì)列 offer(E value)

? ? ? ? 5.2 堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 出隊(duì)列 poll()

? ? ? ? 5.3 堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 查看優(yōu)先級(jí)最大的元素 peek()

????????5.4 堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 判斷該隊(duì)列是否為空

? ? ? ? 5.5 堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 判斷該隊(duì)列是否為滿隊(duì)列

? ? ? ? 5.6 堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列完整代碼

? ? ? ? 1.0 優(yōu)先級(jí)隊(duì)列說(shuō)明

????????優(yōu)先級(jí)隊(duì)列是一種特殊的隊(duì)列，其中每個(gè)元素都有一個(gè)優(yōu)先級(jí)。在優(yōu)先級(jí)隊(duì)列中，具有最高優(yōu)先級(jí)的元素首先被移除。這與普通隊(duì)列不同，普通隊(duì)列是先進(jìn)先出（FIFO）的，而優(yōu)先級(jí)隊(duì)列則是按照優(yōu)先級(jí)來(lái)確定元素的出隊(duì)順序。

????????優(yōu)先級(jí)隊(duì)列通常用于需要按照優(yōu)先級(jí)處理元素的場(chǎng)景，比如任務(wù)調(diào)度、事件處理等。它可以使用不同的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，最常見(jiàn)的是使用堆（heap）來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列。堆是一種特殊的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，它可以快速找到并移除具有最高（或最低）優(yōu)先級(jí)的元素。

????????優(yōu)先級(jí)隊(duì)列的常見(jiàn)操作包括插入元素、移除具有最高優(yōu)先級(jí)的元素、查看具有最高優(yōu)先級(jí)的元素等。實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的常見(jiàn)算法包括插入時(shí)的堆調(diào)整、移除最高優(yōu)先級(jí)元素后的堆調(diào)整等。

? ? ? ? 2.0 用數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列

????????可以使用數(shù)組來(lái)實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，一種簡(jiǎn)單的實(shí)現(xiàn)方式是使用數(shù)組來(lái)存儲(chǔ)元素，并且按照優(yōu)先級(jí)順序來(lái)維護(hù)數(shù)組。

? ? ? ? 用數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列可分為兩種：無(wú)序數(shù)組實(shí)現(xiàn)、有序數(shù)組實(shí)現(xiàn)。

? ? ? ? 3.0?無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列

? ? ? ? 可以直接簡(jiǎn)單粗暴來(lái)說(shuō)，無(wú)序數(shù)組就是插入元素的時(shí)候不按照優(yōu)先級(jí)進(jìn)行排序，而出隊(duì)列的時(shí)候，嚴(yán)格按照優(yōu)先級(jí)大小進(jìn)行出隊(duì)列。

? ? ? ? 首先，需要實(shí)現(xiàn)隊(duì)列中的接口。比如：入隊(duì)列、出隊(duì)列等。

接口代碼如下：

public interface Queue<E> {

    /**
     * 入隊(duì)操作
     */
    boolean offer(E value);

    /**
     * 出隊(duì)操作
     */
    E poll();

    /**
     * 查看隊(duì)頭元素
     */
    E peek();

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

    /**
     * 判斷是否為滿隊(duì)列
     */
    boolean isFull();
}

? ? ? ? 再接著，設(shè)置優(yōu)先級(jí)元素。

代碼如下：

public interface Priority {

    int priority();

}

public class Entry implements  Priority{
    String string;
    int priority;

    public Entry(String string, int priority) {
        this.string = string;
        this.priority = priority;
    }

    @Override
    public int priority() {
        return priority;
    }

    @Override
    public String toString() {
        return "Entry{" +
                "string='" + string + '\'' +
                ", priority=" + priority +
                '}';
    }
}

? ? ? ? 該設(shè)置的優(yōu)先級(jí)元素需要實(shí)現(xiàn) priority 接口，返回當(dāng)前優(yōu)先級(jí)的大小。

? ? ? ? 成員變量有 Priority[] arr 自定義大小的數(shù)組、size 標(biāo)記當(dāng)前元素的個(gè)數(shù)。

代碼如下：

public class UnorderedPriorityQueue<E extends Priority> implements Queue<E> {

    private Priority[] arr;
    private int size;

    public UnorderedPriorityQueue(int capacity) {
        arr = new Priority[capacity];
    }

}

? ? ? ? 3.1 無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 入隊(duì)列 offer(E value)

? ? ? ? 由于用無(wú)序數(shù)組實(shí)現(xiàn)，元素可直接在數(shù)組尾部入隊(duì)列。

代碼如下：

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        arr[size++] = value;
        return true;
    }

? ? ? ? 注意：在入隊(duì)前，需要判斷是否為滿隊(duì)列。入隊(duì)完后，需要進(jìn)行 size++ 。

? ? ? ? 3.2 無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 出隊(duì)列 poll()

? ? ? ? 根據(jù)元素的優(yōu)先級(jí)大小進(jìn)行出隊(duì)列，首先需要遍歷數(shù)組找到索引為 i 處優(yōu)先級(jí)最大的元素。一般有兩種情況：

? ? ? ? 第一種情況：在索引為 i == size - 1 處找到優(yōu)先級(jí)最大的元素，此時(shí)只需要將 size-- ，然后將其引用置為空 arr[size] = null 。

? ? ? ? 第二種情況：不在索引為 i !=??size - 1 處找到優(yōu)先級(jí)最大的元素。那么需要將索引為 i 的元素被 i + 1 處的元素進(jìn)行覆蓋，長(zhǎng)度為：size - 1 - i 。

代碼如下：

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        //先找到優(yōu)先級(jí)大的點(diǎn)
        int j = 0;
        for (int i = 1; i < size; i++) {
            if (arr[j].priority() < arr[i].priority()) {
                j = i;
            }
        }
        E ret = (E)arr[j];
        if (j < size - 1) {
            System.arraycopy(arr,j+1,arr,j,size - 1 - j);
        }
        size--;
        arr[size] = null;
        return ret;
    }

? ? ? ? 最后需要返回優(yōu)先級(jí)最大的元素，在被置為 null 之前將其進(jìn)行保存。每次出隊(duì)完畢，后需要進(jìn)行 size-- 、置為 null 。

? ? ? ? 3.3?無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 查看隊(duì)列中優(yōu)先級(jí)最大的元素 peek()?

? ? ? ? 相比與出隊(duì)列，找到了優(yōu)先級(jí)最大的元素后，不需要進(jìn)行刪除該優(yōu)先級(jí)最大的元素。

代碼如下：

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        //先找到優(yōu)先級(jí)大的點(diǎn)
        int j = 0;
        for (int i = 1; i < size; i++) {
            if (arr[j].priority() < arr[i].priority()) {
                j = i;
            }
        }
        E ret = (E)arr[j];
        return ret;
    }

? ? ? ? 注意：在查看元素之前需要先判斷是否為空隊(duì)列。

? ? ? ? 3.4 無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 判斷是否為空隊(duì)列

? ? ? ? 若 size == 0 ，則為空隊(duì)列；若不是，則不為空。

代碼如下：

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

? ? ? ? 3.5 無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 判斷是否為滿隊(duì)列

? ? ? ? 若 size == arr.length?時(shí)，則為滿隊(duì)列；若不相等，則不為滿。

代碼如下：

    @Override
    public boolean isFull() {
        return size == arr.length;
    }

????????3.6?無(wú)序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列完整代碼

public class UnorderedPriorityQueue<E extends Priority> implements Queue<E> {

    private Priority[] arr;
    private int size;

    public UnorderedPriorityQueue(int capacity) {
        arr = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        arr[size++] = value;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        //先找到優(yōu)先級(jí)大的點(diǎn)
        int j = 0;
        for (int i = 1; i < size; i++) {
            if (arr[j].priority() < arr[i].priority()) {
                j = i;
            }
        }
        E ret = (E)arr[j];
        if (j < size - 1) {
            System.arraycopy(arr,j+1,arr,j,size - 1 - j);
        }
        size--;
        arr[size] = null;
        return ret;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        //先找到優(yōu)先級(jí)大的點(diǎn)
        int j = 0;
        for (int i = 1; i < size; i++) {
            if (arr[j].priority() < arr[i].priority()) {
                j = i;
            }
        }
        E ret = (E)arr[j];
        return ret;
    }

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

    @Override
    public boolean isFull() {
        return size == arr.length;
    }
}

? ? ? ? 4.0 有序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列

? ? ? ? 相對(duì)于無(wú)序數(shù)組優(yōu)先級(jí)隊(duì)列來(lái)說(shuō)，有序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列入隊(duì)列操作需要按照優(yōu)先級(jí)大小進(jìn)行插入，而出隊(duì)列操作直接在索引為 size - 1 處直接獲取該最大優(yōu)先級(jí)元素。

? ? ? ? 首先，同樣的，需要實(shí)現(xiàn)隊(duì)列中的接口。比如：入隊(duì)列、出隊(duì)列等。

接口代碼如下：

public interface Queue<E> {

    /**
     * 入隊(duì)操作
     */
    boolean offer(E value);

    /**
     * 出隊(duì)操作
     */
    E poll();

    /**
     * 查看隊(duì)頭元素
     */
    E peek();

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

    /**
     * 判斷是否為滿隊(duì)列
     */
    boolean isFull();
}

????????再接著，設(shè)置優(yōu)先級(jí)元素。

代碼如下：

public class Entry implements  Priority{
    String string;
    int priority;

    public Entry(String string, int priority) {
        this.string = string;
        this.priority = priority;
    }

    @Override
    public int priority() {
        return priority;
    }

    @Override
    public String toString() {
        return "Entry{" +
                "string='" + string + '\'' +
                ", priority=" + priority +
                '}';
    }
}

????????成員變量有 Priority[] arr 自定義大小的數(shù)組、size 標(biāo)記當(dāng)前元素的個(gè)數(shù)。

代碼如下：

public class OrderedPriorityQueue<E extends Priority> implements Queue<E>{

    private Priority[] arr;
    private int size;

    public OrderedPriorityQueue(int capacity) {
        arr = new Priority[capacity];
    }

}

? ? ? ? 4.1 有序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 入隊(duì)列 offer(E value)

? ? ? ? 使用有序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)入隊(duì)列，在入隊(duì)列之前從后往前遍歷數(shù)組，找到優(yōu)先級(jí)小于入隊(duì)列的元素優(yōu)先級(jí)，找到即可插入其中。

代碼如下：

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        //先找到優(yōu)先級(jí)比value的優(yōu)先級(jí)大的索引
        int i = size - 1;
        while (i >= 0 && arr[i].priority() > value.priority()) {
            arr[i+1] = arr[i];
            i--;
        }
        arr[i+1] = value;
        size++;
        return true;
    }

? ? ? ? 考慮一種情況，若 size == 0 時(shí)，為空隊(duì)列的時(shí)候，該代碼有無(wú)錯(cuò)誤？

? ? ? ? ? ? ? ? 答案是：沒(méi)有問(wèn)題的，當(dāng) size == 0 時(shí)， 則 i = 0 - 1，i = -1 ， 此時(shí)不會(huì)進(jìn)入循環(huán)直接跳到 arr[i + 1] 處，所以，在這種情況下，該代碼沒(méi)有問(wèn)題。

? ? ? ? 4.2 有序數(shù)組實(shí)現(xiàn)有序隊(duì)列 - 出隊(duì)列 poll()

? ? ? ? 這就相對(duì)于有序數(shù)組入隊(duì)列來(lái)說(shuō)比較簡(jiǎn)單了，直接在索引為 i = size - 1 處，得到優(yōu)先級(jí)最大的元素，然后將 size-- ，再接著?arr[size] 置為 null 。

代碼如下：

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E str = (E)arr[size - 1];
        size--;
        arr[size] = null;
        return str;
    }

? ? ? ? 注意：需要記錄優(yōu)先級(jí)最大的元素并且返回。在出隊(duì)列之前需要判斷該隊(duì)列是否為空隊(duì)列。

? ? ? ? 4.3?有序數(shù)組實(shí)現(xiàn)有序隊(duì)列 - 查看優(yōu)先級(jí)最大的元素 peek()

? ? ? ? 先判斷該隊(duì)列是否為空隊(duì)列，若不是，直接返回該數(shù)組索引為 size - 1 處的元素即可。

代碼如下：

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        E str = (E)arr[size - 1];
        return str;
    }

? ? ? ? 4.4 有序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 判斷隊(duì)列是否為空

? ? ? ? 若 size == 0 ，則為空；若不為，則為不空。

代碼如下：

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

? ? ? ? 4.5 有序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 判斷隊(duì)列是否為滿隊(duì)列

? ? ? ? 若 size == arr.length 時(shí)，則為滿隊(duì)列；若不是，則為不滿隊(duì)列。

代碼如下：

    @Override
    public boolean isFull() {
        return size == arr.length;
    }

? ? ? ? 4.6 有序數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列完整代碼

public class OrderedPriorityQueue<E extends Priority> implements Queue<E>{

    private Priority[] arr;
    private int size;

    public OrderedPriorityQueue(int capacity) {
        arr = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        //先找到優(yōu)先級(jí)比value的優(yōu)先級(jí)大的索引
        int i = size - 1;
        while (i >= 0 && arr[i].priority() > value.priority()) {
            arr[i+1] = arr[i];
            i--;
        }
        arr[i+1] = value;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E str = (E)arr[size - 1];
        size--;
        arr[size] = null;
        return str;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        E str = (E)arr[size - 1];
        return str;
    }

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

    @Override
    public boolean isFull() {
        return size == arr.length;
    }
}

? ? ? ? 5.0 大頂堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列

? ? ? ? 大頂堆說(shuō)明：

????????大頂堆是一種特殊的堆，它是一種完全二叉樹(shù)，其中每個(gè)父節(jié)點(diǎn)的值都大于或等于其左右子節(jié)點(diǎn)的值。在大頂堆中，根節(jié)點(diǎn)的值是整個(gè)堆中最大的。

????????大頂堆可以使用數(shù)組來(lái)實(shí)現(xiàn)，其中堆的根節(jié)點(diǎn)存儲(chǔ)在數(shù)組的第一個(gè)位置，然后按照完全二叉樹(shù)的性質(zhì)依次存儲(chǔ)其他節(jié)點(diǎn)。這種實(shí)現(xiàn)方式使得大頂堆的父節(jié)點(diǎn)和子節(jié)點(diǎn)之間可以通過(guò)簡(jiǎn)單的數(shù)學(xué)關(guān)系來(lái)計(jì)算，從而方便進(jìn)行堆調(diào)整操作。假設(shè) i 不為 0 ，該雙親索引為：（i - 1）/ 2 ；該左孩子為：2 * i + 1；該右孩子為：2 * i? + 2 。

????????首先，需要實(shí)現(xiàn)隊(duì)列中的接口。比如：入隊(duì)列、出隊(duì)列等。

接口代碼如下：

public interface Queue<E> {

    /**
     * 入隊(duì)操作
     */
    boolean offer(E value);

    /**
     * 出隊(duì)操作
     */
    E poll();

    /**
     * 查看隊(duì)頭元素
     */
    E peek();

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

    /**
     * 判斷是否為滿隊(duì)列
     * */
    boolean isFull();
}

?????????再接著，設(shè)置優(yōu)先級(jí)元素。

代碼如下：

public class Entry implements  Priority{
    String string;
    int priority;

    public Entry(String string, int priority) {
        this.string = string;
        this.priority = priority;
    }

    @Override
    public int priority() {
        return priority;
    }

    @Override
    public String toString() {
        return "Entry{" +
                "string='" + string + '\'' +
                ", priority=" + priority +
                '}';
    }
}

????????成員變量有 Priority[] arr 自定義大小的數(shù)組、size 標(biāo)記當(dāng)前元素的個(gè)數(shù)。

代碼如下：

public class BigTopPile<E extends Priority> implements Queue<E> {

    private Priority[] arr;
    private int size;

    public BigTopPile(int capacity) {
        arr = new Priority[capacity];
    }

}

? ? ? ? 5.1 堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 入隊(duì)列 offer(E value)

? ? ? ? 具體思路為：由于是按照優(yōu)先級(jí)大小來(lái)存放元素的，所以，需要先比較優(yōu)先級(jí)大小，在適合的位置插入?，F(xiàn)在已知 i = size，該雙親為：（i - 1）/ 2 。接下來(lái)，需要判斷 arr[（i - 1）/ 2] 的優(yōu)先級(jí)于入隊(duì)列的元素優(yōu)先級(jí)大小，若 arr[（i - 1）/ 2] 的優(yōu)先級(jí)較大，此時(shí)該入隊(duì)列的元素存放的位置為 arr[i] = value ；若 value 的優(yōu)先級(jí)大于當(dāng)前 arr[（i - 1）/ 2] 時(shí)，先將當(dāng)前 arr[（i - 1）/ 2] 往后放，即 arr[i] = arr[（i - 1）/ 2] 。之后需要繼續(xù)往上找雙親，將 i = (i - 1) / 2 ，直到 i == 0 或者 value 的優(yōu)先級(jí)小于當(dāng)前 arr[（i - 1）/ 2] 時(shí)，則為 arr[i] = value 。

代碼如下：

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        int i = size;
        int j = (i - 1) / 2;
        while (i > 0 && arr[j].priority() < value.priority()) {
            arr[i] = arr[j];
            i = j;
            j = (i - 1) / 2;
        }
        arr[i] = value;
        size++;
        return true;
    }

? ? ? ? 只要 i == 0 時(shí)， j 不能繼續(xù)往上走了，否則為拋空指針異常。

? ? ? ? 5.2 堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 出隊(duì)列 poll()

? ? ? ? 具體思路為：分為兩步。

? ? ? ? 第一步，將 arr[size - 1] 處的元素交換到 arr[0] 處。

? ? ? ? 第二步，由于根處的優(yōu)先級(jí)永遠(yuǎn)都要大于該孩子的優(yōu)先級(jí)，所以，將交換之后的元素進(jìn)行下潛，即先找到該左右孩子優(yōu)先級(jí)最大的元素，于根元素進(jìn)行交換，一直往下進(jìn)行下潛。直到該根元素沒(méi)有左右孩子或者根元素的優(yōu)先級(jí)都大于該左右孩子的優(yōu)先級(jí)。

代碼實(shí)現(xiàn)：

非遞歸實(shí)現(xiàn)：

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }

        E top = (E)arr[0];
        arr[0] = arr[size - 1];
        size--;
        arr[size] = null;
        int i = 0;
        while ( (i * 2 + 1) < size && (i * 2 + 2) < size && (arr[i].priority() < arr[i * 2 + 1].priority() || arr[i].priority() < arr[i * 2 + 2].priority() ) ) {

            int j = 0;
            if (arr[i * 2 + 1].priority() > arr[i * 2 + 2].priority()) {
                j = i * 2 + 1;
            }else if (arr[i * 2 + 1].priority() <= arr[i * 2 + 2].priority()) {
                j = i * 2 + 2;
            }
            E temp = (E)arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i = j;
        }
        return top;
    }

?????????(i * 2 + 1) < size && (i * 2 + 2) < size 該代碼判斷的是有無(wú)左右孩子元素。

遞歸實(shí)現(xiàn)：

    public E poll1() {
        if (isEmpty()) {
            return null;
        }
        //交換頭尾
        swap(0,size - 1);
        size--;
        //置為 null
        E ret = (E)arr[size];
        arr[size] = null;

        //下潛
        down(0);
        return ret;

    }
    private void swap(int i, int j) {
        E t = (E)arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    private void down(int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int max = i;
        if ( left < size && arr[max].priority() < arr[left].priority()) {
            max = left;
        }
        if (right < size && arr[max].priority() < arr[right].priority()) {
            max = right;
        }
        if (max != i) {
            swap(max,i);
            down(max);
        }
    }

????????

? ? ? ? 5.3 堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 查看優(yōu)先級(jí)最大的元素 peek()

? ? ? ? 先判斷該隊(duì)列是否為空，若不為空，則直接返回堆頂元素即可。

代碼如下：

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E)arr[0];
    }

? ? ? ? ?5.4 堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 判斷該隊(duì)列是否為空

? ? ? ? 當(dāng) size == 0 時(shí)，則為空隊(duì)列。

代碼實(shí)現(xiàn)：

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

? ? ? ? 5.5 堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 - 判斷該隊(duì)列是否為滿隊(duì)列

? ? ? ? 當(dāng) size == arr.length 時(shí)，則為滿隊(duì)列。

代碼實(shí)現(xiàn)：

    @Override
    public boolean isFull() {
        return size == arr.length;
    }

? ? ? ? 5.6 堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列完整代碼

public class BigTopPile<E extends Priority> implements Queue<E> {

    private Priority[] arr;
    private int size;

    public BigTopPile(int capacity) {
        arr = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        int i = size;
        int j = (i - 1) / 2;
        while (i > 0 && arr[j].priority() < value.priority()) {
            arr[i] = arr[j];
            i = j;
            j = (i - 1) / 2;
        }
        arr[i] = value;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }

        E top = (E)arr[0];
        arr[0] = arr[size - 1];
        size--;
        arr[size] = null;
        int i = 0;
        while ( (i * 2 + 1) < size && (i * 2 + 2) < size && (arr[i].priority() < arr[i * 2 + 1].priority() || arr[i].priority() < arr[i * 2 + 2].priority() ) ) {

            int j = 0;
            if (arr[i * 2 + 1].priority() > arr[i * 2 + 2].priority()) {
                j = i * 2 + 1;
            }else if (arr[i * 2 + 1].priority() <= arr[i * 2 + 2].priority()) {
                j = i * 2 + 2;
            }
            E temp = (E)arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i = j;
        }
        return top;
    }

    public E poll1() {
        if (isEmpty()) {
            return null;
        }
        //交換頭尾
        swap(0,size - 1);
        size--;
        //置為 null
        E ret = (E)arr[size];
        arr[size] = null;

        //下潛
        down(0);
        return ret;

    }
    private void swap(int i, int j) {
        E t = (E)arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    private void down(int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int max = i;
        if ( left < size && arr[max].priority() < arr[left].priority()) {
            max = left;
        }
        if (right < size && arr[max].priority() < arr[right].priority()) {
            max = right;
        }
        if (max != i) {
            swap(max,i);
            down(max);
        }
    }



    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E)arr[0];
    }

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

    @Override
    public boolean isFull() {
        return size == arr.length;
    }
}

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-763288.html

到了這里，關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)篇-用數(shù)組、堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！