Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊列(PriorityQueue)用法詳解

更新時間：2022年07月13日 14:54:39 作者：XH學(xué)Java

優(yōu)先級隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)，操作的數(shù)據(jù)帶有優(yōu)先級，這種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級隊列（PriorityQueue）。本文將詳細講講Java優(yōu)先級隊列的用法，感興趣的可以了解一下

概念

優(yōu)先級隊列是一種先進先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，與隊列不同的是，操作的數(shù)據(jù)帶有優(yōu)先級，通俗的講就是可以比較大小，在出隊列的時候往往需要優(yōu)先級最高或者最低的元素先出隊列，這種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級隊列（PriorityQueue）

PriorityQueue的使用

構(gòu)造方法

這里只介紹三種常用的構(gòu)造方法

構(gòu)造方法	說明
PriorityQueue()	不帶參數(shù)，默認容量為11
PriorityQueue(int initialCapacity)	參數(shù)為初始容量，該初始容量不能小于1
PriorityQueue(Collection<? extends E> c)	參數(shù)為一個集合

代碼展示：

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
 
public class TestPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> p1 = new PriorityQueue<>(); //容量默認為11
        PriorityQueue<Integer> p2 = new PriorityQueue<>(10); //參數(shù)為初始容量
        List<Integer> list = new ArrayList<>();
        list.add(0);
        list.add(1);
        list.add(2);
        PriorityQueue<Integer> p3 = new PriorityQueue<>(list); //使用集合list作為參數(shù)構(gòu)造優(yōu)先 
                                                               // 級隊列
    }
}

常用方法

方法	說明
boolean offer(E e)	插入元素e，返回是否插入成功，e為null，會拋異常
E peek()	獲取堆（后面介紹堆）頂元素，如果隊列為空，返回null
E poll()	刪除堆頂元素并返回，如果隊列為空，返回null
int size()	獲取有效元素個數(shù)
void clear()	清空隊列
boolean isEmpty()	判斷隊列是否為空

offer方法的測試

        PriorityQueue<Integer> p = new PriorityQueue<>();
        p.offer(1);
        p.offer(2);
        p.offer(3);
        System.out.println(p.size());
        p.offer(null);

打印結(jié)果：

1，2，3都正常插入，但是插入null的時候，報了NullPointerException空指針異常

peek與poll方法的測試

        PriorityQueue<Integer> p = new PriorityQueue<>();
        p.offer(1);
        p.offer(2);
        p.offer(3);
        System.out.println(p.peek());
        System.out.println(p.poll());
        System.out.println(p.size());
        p.clear();
        System.out.println(p.peek());
        System.out.println(p.poll());

打印結(jié)果：

默認是小堆，所以堆頂元素是1，獲取到1，在刪除1，剩余元素個數(shù)為兩個，當隊列為空的時候，這兩個方法都返回null

size，isEmpty，clear方法的測試

        PriorityQueue<Integer> p = new PriorityQueue<>();
        p.offer(1);
        p.offer(2);
        p.offer(3);
        System.out.println(p.size());
        System.out.println(p.isEmpty());
        p.clear();
        System.out.println(p.isEmpty());

打印結(jié)果：

打印元素個數(shù)為3，所以不為空輸出false，清空后，隊列為空，輸出true

注意事項

PriorityQueue中存放的元素必須能比較大小，不能比較大小的對象不能插入，會拋出ClassCastException異常

例如：向優(yōu)先級隊列中插入兩個學(xué)生類型的數(shù)據(jù)

class Student {
    private String name;
    private int age;
 
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
}
 
public class Test {
    public static void main(String[] args) {
        Student s1 = new Student("張三",25);
        Student s2 = new Student("李四",30);
        PriorityQueue<Student> p = new PriorityQueue();
        p.offer(s1);
        p.offer(s2);
    }
}

結(jié)果：報了類型轉(zhuǎn)換異常的錯誤，因為student類型不能直接比較大小

如果想比較兩個自定類型的大小，請參考Java中對象的比較這篇文章

不能插入null對象，否則會拋NullPointerException異常
內(nèi)部可以自動擴容
PriorityQueue底層使用堆數(shù)據(jù)結(jié)構(gòu)
PriorityQueue默認是小堆，如果想要創(chuàng)建大堆可以使用如下方式創(chuàng)建：

        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

注意：o2-o1是創(chuàng)建大堆，o1-o2是創(chuàng)建小堆

PriorityQueue的擴容方式

以下是JDK1.8中擴容的方式：

說明：

如果容量小于64，按照oldCapacity的2倍擴容
如果容量大于等于64，按照oldCapacity的1.5倍擴容
如果容量超過MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE擴容

小試牛刀（最小k個數(shù)）

題目

方法：創(chuàng)建一個優(yōu)先級隊列，獎數(shù)組中的元素依次放入該優(yōu)先級隊列中，在依次從該優(yōu)先級隊列取出k個即可

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(k == 0 || arr.length==0){
            return ret;
        }
        PriorityQueue<Integer> p = new PriorityQueue<>(arr.length);
        for(int i = 0;i < arr.length;i++){
            p.offer(arr[i]);
        }
        for(int i = 0;i < k;i++){
            ret[i] = p.poll();
        }
        return ret;
    }
}

堆的介紹

JDK1.8中PriorityQueue底層采用了堆數(shù)據(jù)結(jié)構(gòu)，堆其實就是對完全二叉樹的元素作出了一些調(diào)整

所謂堆就是將一組數(shù)據(jù)按照完全二叉樹的順序存儲方式存儲，保證每一個根結(jié)點元素大于它的孩子結(jié)點的元素（大根堆）或者小于它的孩子結(jié)點的元素（小根堆）

堆的性質(zhì)

堆中某個結(jié)點的值總是不大于或著不小于其父節(jié)點的值

堆是一顆完全二叉樹

堆的創(chuàng)建

此處我們創(chuàng)建小堆，以21，15，19，17，18，23，25為例

發(fā)現(xiàn)上述序列根的左右子樹都已經(jīng)滿足小堆的特性，故只需要將根結(jié)點向下調(diào)整即可

向下調(diào)整的過程：

1. 用parent標記要被調(diào)整的結(jié)點，child標記parent的左孩子

2. 如果左孩子存在，即child<size,size為序列元素的個數(shù)，進行以下操作，直到左孩子不存在

判斷parent右孩子是否存在，如果存在讓child標記兩個孩子最小的孩子
如果parent小于child，則將parent與child標記的元素交換位置，如果parent大于child，說明此時已經(jīng)滿足小堆的特性
讓parent=child，child=parent*2+1，循環(huán)步驟2，直到不滿足步驟2的條件

代碼展示：

    public void shiftDown(int[] array,int parent){
        int child = parent*2+1;
        int size = array.length;
        while(child < size){
            if(child+1<size && array[child]>array[child+1]){
                child = child+1;
            }
            if(array[parent] > array[child]){
                swap(array,parent,child);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }

注意：在調(diào)整以parent為根的二叉樹時，必須滿足parent的左右子樹滿足堆的特性，此時才能向下調(diào)整parent

時間復(fù)雜度分析：最壞情況從根比到葉子，比較的次數(shù)為二叉樹的高度，故時間復(fù)雜度為O(log2N)

那么對于普通的序列如1，5，3，8，7，6，即根節(jié)點的左右子樹不滿足大堆的特性，該如何調(diào)整？

方法：從倒數(shù)第一個非葉子結(jié)點開始調(diào)整，直到調(diào)整到根

代碼展示：

    public void createHeap(int[] array){
        int root = (array.length-2)>>1;
        for(;root>=0;root--){
            shiftDown(array,root);
        }
    }

創(chuàng)建堆的時間復(fù)雜度

故建堆的時間復(fù)雜度為O(N)

堆的插入

堆的插入分為兩步：

將元素插入隊列尾部，如果空間不夠需要擴容
將新插入的結(jié)點向上調(diào)整，直到滿足堆的特性

例如：給大堆8，7，6，5，1，3插入9

代碼展示：

    public void shiftUp(int[] array,int child){
        int parent = (child-1)/2;
        while(child > 0){
            if(array[child] < array[parent]){
                break;
            }else {
                swap(array,parent,child);
                child = parent;
                parent = (child-1)/2;
            }
        }
    }

堆的刪除

堆刪除的是堆頂元素

刪除步驟：

交換堆頂與堆最后一個元素的位置
將堆中的有效元素個數(shù)減少一個
將堆頂元素向下調(diào)整

代碼展示：

    public int poll(){
        int oldVal = array[0];
        array[0] = array[array.length-1];
        size--;
        shiftDown(array,0);
        return oldVal;
    }

優(yōu)先級隊列的模擬實現(xiàn)

此處用小堆實現(xiàn)優(yōu)先級隊列，并且隊列中保存的元素為Integer類型

準備工作包括：構(gòu)造方法，向上調(diào)整，向下調(diào)整，交換

public class MyPriorityQueue {
    Integer[] array;
    int size;
    public MyPriorityQueue(){
        array = new Integer[11];
        size = 0;
    }
    public MyPriorityQueue(int initCapacity){
        if(initCapacity < 1){
            throw new IllegalArgumentException("初始容量小于1");
        }
        array = new Integer[initCapacity];
        size = 0;
    }
    public MyPriorityQueue(Integer[] arr){
        array = new Integer[arr.length];
        for(int i = 0;i < arr.length;i++){
            array[i] = arr[i];
        }
        size = arr.length;
        int lastLeafParent = (size-2)/2;
        for(int root = lastLeafParent;root >= 0;root--){
            shiftDown(root);
        }
    }
    public void shiftDown(int parent){
        int child = parent*2+1;
        while(child < size){
            if(child+1<size && array[child+1]<array[child]){
                child = child+1;
            }
            if(array[parent] > array[child]){
                swap(parent,child);
                parent = child;
                child = parent*2+1;
            }else {
                return;
            }
        }
    }
    public void shiftUp(int child){
        int parent = (child-1)/2;
        while(child > 0){
            if(array[child] < array[parent]){
                swap(child,parent);
                child = parent;
                parent = (child-1)/2;
            }else {
                return;
            }
        }
    }
    public void swap(int a,int b){
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }
}

插入

    public boolean offer(Integer e){
        if(e == null){
            throw new NullPointerException("插入的元素為null");
        }
        ensureCapacity();
        array[size++] = e;
        shiftUp(size-1);
        return true;
    }
    private void ensureCapacity(){
        if(array.length == size){
            int newCapacity = array.length*2;
            array = Arrays.copyOf(array,newCapacity);
        }
    }

注意：插入前需要判斷是否擴容，此處擴容按照2倍方式擴容

刪除

    public Integer poll(){
        if(isEmpty()){
            return null;
        }
        Integer ret = array[0];
        swap(0,size-1);
        shiftDown(0);
        return ret;
    }

獲取堆頂元素

    public Integer peek(){
        if(isEmpty()){
            return null;
        }
        Integer ret = array[0];
        return ret;
    }

獲取有效元素個數(shù)

    public int size(){
        return size;
    }

判空

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

清空

    public void clear(){
        size = 0;
    }

堆的應(yīng)用

PriorityQueue的實現(xiàn)，PriorityQueue底層采用堆數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的
堆排序，詳見基本排序算法總結(jié)(Java實現(xiàn))
Top-k問題

Top-k問題

即求數(shù)據(jù)中前k個最大或者最小元素，一般情況下數(shù)據(jù)量都會比較大

如果數(shù)據(jù)量大使用排序那種方法就不可取了，那么如何解決呢？

1. 使用數(shù)據(jù)中前k個數(shù)據(jù)建堆

求前k個最大，建小堆

求前k個最小，建大堆

2. 用剩余的元素依次與堆頂元素比較

求前k個最大，若比堆頂元素大，則替換小堆堆頂元素

求前k個最小，若比堆頂元素小，則替換大堆堆頂元素

以上就是Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊列(PriorityQueue)用法詳解的詳細內(nèi)容，更多關(guān)于Java優(yōu)先級隊列的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

軟件下載

源碼下載

軟件編程

網(wǎng)絡(luò)編程

在線工具

數(shù)據(jù)庫

CMS

常用工具

Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊列(PriorityQueue)用法詳解

目錄

概念

PriorityQueue的使用

小試牛刀（最小k個數(shù)）

堆的介紹

優(yōu)先級隊列的模擬實現(xiàn)

Top-k問題

相關(guān)文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具