【Java 資料結構】 優先級隊列（堆）

學習目标：

目标：熟練掌握Java所學知識

學習内容：

本文内容：優先級隊列（堆）

文章目錄

• 學習目标：
• 學習内容：
• 一、優先級隊列
• • 1.1 概念
  • 1.2常用接口介紹
  • • 1.2.1 PriorityQueue特性
    • 1.2.2 PriorityQueue常用接口介紹
  • 1.3 優先級隊列的應用
• 二、優先級隊列的模拟實作
• • 2.1堆的概念
  • 2.2堆的存儲方式
  • 2.3 堆的建立
  • • 2.3.1 堆向下調整
    • 2.3.2 堆的向上調整
    • 2.3.3删除堆頂元素
    • 2.3.4取堆頂元素

一、優先級隊列

1.1 概念

隊列是一種先進先出的資料結構(FIFO)。但是有些情況下，操作的資料可能帶有優先級，出隊列時，可能需要優先級高的先出隊列，在該場景下，顯然不能使用普通隊列；

比如： 用手機看視訊時，這時有電話打進來，系統就會優先處理打進來的電話

在這種情況下，我們的資料結構應該提供兩個基本操作，一個是傳回優先級最高的對象，一個是添加新的對象。這種資料結構成為優先級隊列

1.2常用接口介紹

1.2.1 PriorityQueue特性

Java集合提供了PriorityQueue和PriorityBlockingQueqe兩種類型的優先級隊列，PriorityQueue是線程不安全的，PriorityBlockingQueue是線程安全的

1. 使用時必須導入PriorityQueue所在的包，即

import java.util.PriorityQueue

1. PriorityQueue中放的元素必須能夠比較大小，不能插入無法比較大小的元素，否則會抛出ClassCastException異常;
2. 不能插入null對象，否則會抛出NullPointerException異常;
3. 沒有容量限制，可以插入任意多個元素，其内部可以自動擴容;
4. 插入和删除元素的時間複雜度都是O㏒(2N);
5. PriorityQueue底層使用的堆資料結構（堆 後文會介紹到）

1.2.2 PriorityQueue常用接口介紹

1. 優先級隊列的構造

構造器	功能介紹
PriorityQueue	建立一個空的優先級隊列，預設容量是11
PriorityQueue(int initialCapacity)	建立一個初始容量為initialCapacity大小的優先級隊列
PriorityQueue(Collection<?extends E>c)	用一個集合來初始化優先級隊列

public class TestPriorityQueue {
   public static void main(String[] args) {
       //建立一個空的優先級隊列，預設容量為11
       PriorityQueue<Integer> q1=new PriorityQueue<>();

       //建立一個空的優先級隊列，底層的容量為100
       PriorityQueue<Integer> q2=new PriorityQueue<>();

       ArrayList<Integer> list =new ArrayList<>();
       list.add(1);
       list.add(2);
       list.add(3);

       //用一個ArrayList對象構造優先級隊列
       //此時優先級隊列已經有3個元素
       PriorityQueue<Integer> q3=new PriorityQueue<>(list);
   }
}
           

1. 優先級隊列的常用方法

函數名	功能
boolean offer(E e)	插入元素e，插入成功傳回true。如果e為空，則抛出NullPointerException異常，時間複雜度為O㏒(2N),空間不夠時會自動擴容
E peek()	擷取優先級最高的元素，入隊優先級隊列為空，則傳回null
E poll()	移除優先級最高的元素并傳回，如果優先級隊列為空則傳回null
int size()	擷取有效元素個數
void clear()	清空優先級隊列
boolean isEmpty()	檢測優先級隊列是否為空，為空則傳回true

public static void testPriorityQueue2(){
        int[] arr={9,5,2,7,4,8,3,6};

        //如果知道元素個數，可以在建立優先級隊列時，直接将容量設定好
        //否則在插入時會有不必要的擴容操作，效率較低
        PriorityQueue<Integer> q=new PriorityQueue<>(arr.length);
        //将數組元素插入到優先級隊列中
        for(int i:arr){
            q.offer(i);
        }

        //擷取優先級最高的元素
        System.out.println(q.peek());//運作結果  2
        //擷取優先級隊列有效元素個數
        System.out.println(q.size());//運作結果  8

        q.poll();//删除優先級隊列中優先級最高的元素

        System.out.println(q.peek());//運作結果  3
        System.out.println(q.size());//運作結果  7

        q.offer(0);//插入元素0
        System.out.println(q.peek());//運作結果  0

    }

           

1.3 優先級隊列的應用

top-k問題：最小的k個數

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr==null||k<=0){
            return new int[0];
        }
        PriorityQueue<Integer> queue=new PriorityQueue<>(arr.length);
        //将數組元素插入優先級隊列中
        for(int i=0;i<arr.length;i++){
            queue.offer(arr[i]);
        }
        int[] res=new int[k];
        //得到優先級隊列的前k個數
        for(int i=0;i<k;i++){
            res[i]=queue.poll();
        }
        return res;
    }
}
           

二、優先級隊列的模拟實作

2.1堆的概念

如果有一個關鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹的順序存儲方式存儲

在一個一維數組中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，則稱為小堆(或大堆)。

将根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。

2.2堆的存儲方式

2.3 堆的建立

2.3.1 堆向下調整

這個代碼是以小堆為例

public static void shiftDown(int[] arr, int index, int size) {
        int parent = index;//需要調整的位置
        int child = 2 * parent + 1;//chile标記parent的左孩子節點
        while (child < size) {
            if (child + 1 < size && arr[child] > arr[child + 1]) {
                //判斷parent左右孩子的大小關系，讓child标記較大的孩子節點
                child = child + 1;
            }
            //判斷parent和child位置的元素的大小關系，
            //如果arr[child] < arr[parent]，則交換位置
            if (arr[child] < arr[parent]) {
                int tmp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = tmp;
            } else {
                //否則arr[parent]就已經找到了合适的位置結束循環
                break;
            }
            parent = child;//更新parent标記的位置
            child = 2 * parent + 1;//更新child标記的位置,繼續下次循環
        }
    }
           

2.3.2 堆的向上調整

同樣是以小堆為例

public  void shiftUp(int[] arr, int size, int index) {
        int child = index;//讓child标記要調整元素的位置
        int parent = (child - 1) / 2;//child位置的父親位置
        while (child > 0) {
            //如果arr[child] < arr[parent]，則交換位置
            if (arr[child] < arr[parent]) {
                int temp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = temp;
            } else {
                //否則就找到的index位置元素該在的位置
                break;
            }
            child = parent;//更新child位置，進行下次循環
            parent = (child - 1) / 2;//更新parent位置，進行下次循環
        }
    }
           

2.3.3删除堆頂元素

删除堆頂元素可直接将堆頂元素與最後一個元素交換，将堆的有效元素個數減一，然後對堆頂元素進行向下調整即可

public  Integer poll() {
        if (size == 0) {
            return null;
        }
        int res = arr[0];
        //交換操作
        int temp = arr[0];
        arr[0] = arr[size - 1];
        arr[size - 1] = temp;
        size--;//堆的有效元素個數減一就實作了删除元素
        shiftDown(arr, 0, size);//對堆頂元素進行向下調整
        return res;
    }
           

2.3.4取堆頂元素

public  Integer peek() {
        if (size == 0) {
            return null;
        }
        int res = arr[0];
        return res;
    }