Java資料結構之優先順序佇列(PriorityQueue)用法詳解

2022-07-13 18:03:36

概念

優先順序佇列是一種先進先出（FIFO）的資料結構，與佇列不同的是，操作的資料帶有優先順序，通俗的講就是可以比較大小，在出佇列的時候往往需要優先順序最高或者最低的元素先出佇列，這種資料結構就是優先順序佇列（PriorityQueue）

PriorityQueue的使用

構造方法

這裡只介紹三種常用的構造方法

構造方法	說明
PriorityQueue()	不帶引數，預設容量為11
PriorityQueue(int initialCapacity)	引數為初始容量，該初始容量不能小於1
PriorityQueue(Collection<? extends E> c)	引數為一個集合

程式碼展示：

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); //引數為初始容量
        List<Integer> list = new ArrayList<>();
        list.add(0);
        list.add(1);
        list.add(2);
        PriorityQueue<Integer> p3 = new PriorityQueue<>(list); //使用集合list作為引數構造優先 
                                                               // 級佇列
    }
}

常用方法

方法	說明
boolean offer(E e)	插入元素e，返回是否插入成功，e為null，會拋異常
E peek()	獲取堆（後面介紹堆）頂元素，如果佇列為空，返回null
E poll()	刪除堆頂元素並返回，如果佇列為空，返回null
int size()	獲取有效元素個數
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);

列印結果：

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());

列印結果：

預設是小堆，所以堆頂元素是1，獲取到1，在刪除1，剩餘元素個數為兩個，當佇列為空的時候，這兩個方法都返回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());

列印結果：

列印元素個數為3，所以不為空輸出false，清空後，佇列為空，輸出true

注意事項

PriorityQueue中存放的元素必須能比較大小，不能比較大小的物件不能插入，會丟擲ClassCastException異常

例如：向優先順序佇列中插入兩個學生型別的資料

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);
    }
}

結果：報了型別轉換異常的錯誤，因為student型別不能直接比較大小

如果想比較兩個自定型別的大小，請參考Java中物件的比較這篇文章

不能插入null物件，否則會拋NullPointerException異常
內部可以自動擴容
PriorityQueue底層使用堆資料結構
PriorityQueue預設是小堆，如果想要建立大堆可以使用如下方式建立：

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

注意：o2-o1是建立大堆，o1-o2是建立小堆

PriorityQueue的擴容方式

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

說明：

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

小試牛刀（最小k個數）

題目

方法：建立一個優先順序佇列，獎陣列中的元素依次放入該優先順序佇列中，在依次從該優先順序佇列取出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底層採用了堆資料結構，堆其實就是對完全二元樹的元素作出了一些調整

所謂堆就是將一組資料按照完全二元樹的順序儲存方式儲存，保證每一個根結點元素大於它的孩子結點的元素（大根堆）或者小於它的孩子結點的元素（小根堆）

堆的性質

堆中某個結點的值總是不大於或著不小於其父節點的值

堆是一顆完全二元樹

堆的建立

此處我們建立小堆，以21，15，19，17，18，23，25為例

發現上述序列根的左右子樹都已經滿足小堆的特性，故只需要將根結點向下調整即可

向下調整的過程：

1. 用parent標記要被調整的結點，child標記parent的左孩子

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

判斷parent右孩子是否存在，如果存在讓child標記兩個孩子最小的孩子
如果parent小於child，則將parent與child標記的元素交換位置，如果parent大於child，說明此時已經滿足小堆的特性
讓parent=child，child=parent*2+1，迴圈步驟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;
            }
        }
    }

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

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

那麼對於普通的序列如1，5，3，8，7，6，即根節點的左右子樹不滿足大堆的特性，該如何調整？

方法：從倒數第一個非葉子結點開始調整，直到調整到根

程式碼展示：

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

建立堆的時間複雜度

故建堆的時間複雜度為O(N)

堆的插入

堆的插入分為兩步：

將元素插入佇列尾部，如果空間不夠需要擴容
將新插入的結點向上調整，直到滿足堆的特性

例如：給大堆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;
            }
        }
    }

堆的刪除

堆刪除的是堆頂元素

刪除步驟：

交換堆頂與堆最後一個元素的位置
將堆中的有效元素個數減少一個
將堆頂元素向下調整

程式碼展示：

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

優先順序佇列的模擬實現

此處用小堆實現優先順序佇列，並且佇列中儲存的元素為Integer型別

準備工作包括：構造方法，向上調整，向下調整，交換

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;
    }

獲取有效元素個數

    public int size(){
        return size;
    }

判空

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

清空

    public void clear(){
        size = 0;
    }

堆的應用

PriorityQueue的實現，PriorityQueue底層採用堆資料結構實現的
堆排序，詳見基本排序演演算法總結(Java實現)
Top-k問題

Top-k問題

即求資料中前k個最大或者最小元素，一般情況下資料量都會比較大

如果資料量大使用排序那種方法就不可取了，那麼如何解決呢？

1. 使用資料中前k個資料建堆

求前k個最大，建小堆

求前k個最小，建大堆

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

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

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

以上就是Java資料結構之優先順序佇列(PriorityQueue)用法詳解的詳細內容，更多關於Java優先順序佇列的資料請關注it145.com其它相關文章！

Java資料結構之優先順序佇列(PriorityQueue)用法詳解

目錄

概念

PriorityQueue的使用

小試牛刀（最小k個數）

堆的介紹

優先順序佇列的模擬實現

Top-k問題

熱門文章