優先級隊列------堆（Heap）

一、三種堆的差別：

1、 優先級隊列（堆）：是一種特殊的資料結構，本質上是一個完全二叉樹

2、Java中的"堆"：JVM持有的記憶體中的一個記憶體區域

3、作業系統中的"堆"：每個程序也持有一定的記憶體空間，在這上面也有一個記憶體區域叫做堆

- 優先級隊列：

優先級隊列也是一個隊列，但不是單純的先進先出，而是把優先級最高的先出去，該隊列内部的結構就是’堆’

- 常用接口

1、PriorityQueue

1)單純的整形優先級隊列入隊和出隊—按照數字大小順序來出隊

import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        //建立一個優先級隊列
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        //建立一個數組
        int[] arr={4,6,1,2};
        for(int x:arr){
            //入隊列
            queue.offer(x);
        }
        while(!queue.isEmpty()){
            //出隊
            System.out.println(queue.poll());
        }
    }
}
           

2）對象在一個類中的比較

例如：建立一個BoyFriend類

import java.util.PriorityQueue;


class BoyFriend{
        public String name;
        public int age;
        public int money;
        public int face;

        public BoyFriend(String name, int age, int money, int face) {
            this.name = name;
            this.age = age;
            this.money = money;
            this.face = face;
        }
    }
    public class Test {

        public static void main(String[] args) {
            BoyFriend[] arr={
                    new BoyFriend("張三",20,10,100),
                    new BoyFriend("李四",40,80,50),
                    new BoyFriend("王五",50,100,10),
            };
            //建立一個優先級隊列
            PriorityQueue<BoyFriend> queue=new PriorityQueue<>();
            for(BoyFriend x:arr){
                queue.offer(x);
            }
            while(!queue.isEmpty()){
                BoyFriend cur=queue.poll();
                System.out.println(cur.name);
            }
        }
    }


           

**注意：**此時會抛出一個異常

------向下轉型異常

• **Comparable<>**是标準庫内置的一個“接口”（帶泛型參數，用來指定兩個對象之間的大小關系，用來定義比較規則），裡面有一個抽象方法*compare To(Object other)，*通過這個方法來指定對象自身和另外一個對象之間的大小關系(即比較this和other之間的大小關系)

  this<other,傳回一個<0的值

  this >other,傳回一個>0的值

  this=other,傳回一個=0的值

修改結果：

1）利用Comparable接口—哪個類需要比較，就讓這個類實作該接口（隻能實作隻有一種比較規則的情況—即隻能用一次（eg:money））

class BoyFriend implements Comparable<BoyFriend>{
        public String name;
        public int age;
        public int money;
        public int face;

        public BoyFriend(String name, int age, int money, int face) {
            this.name = name;
            this.age = age;
            this.money = money;
            this.face = face;
        }

        //實作Comparable裡的抽象方法
    @Override
    public int compareTo(BoyFriend o) {
        //将目前對象和o進行比較
        //注意：此處的減數和被減數不用刻意去記，可根據結果進行調整
        //根據錢的多少來比較
        return o.money-this.money;
    }
}
           

2）利用 Comparator接口—定義一個新的類，實作該接口，裡面的compare方法的參數是兩個對應要比較的類（更加适用于指定了多種比較規則的情況—可建立多個Comparator，用到哪個的時候就使用哪個）

//接口裡的參數是要被比較的類
class BoyFriendComparator implements Comparator<BoyFriend>{
    @Override
    public int compare(BoyFriend o1, BoyFriend o2) {
        return o1.money-o2.money;
    }
}
           

二、 優先級隊列的應用

• 用來排序（堆排序）
• 用來解決topk問題（找出前k個最大或者最小元素）

1、堆

1）堆的分類：

分為大堆、小堆

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

2）堆的性質：

.堆中某個節點的值總是不大于或者不小于其父節點的值

.堆總是一顆完全二叉樹

3）用途：

能夠高效的擷取到最大值/最小值，也能高效擷取到第二大/第二小…

4）堆的存儲

堆實質上是一個完全二叉樹，一般是使用數組(下标從0開始)來存儲這個二叉樹的

對于這種存儲方式，尋找雙親結點和孩子結點的方式(直接計算下标)：

…如果i=0，則i表示的結點為根節點，否則i的雙親結點為（i-1）/2

…如果2i+1小于節點個數，則節點i的左孩子下标為2i+1，否則沒有左孩子

…如果2i+2小于節點個數，則節點i的右孩子下标為2i+2，否則沒有右孩子

…最後一個節點的父節點下标為：（（length-1）-1）/2

2、堆的建立

• 給定一個數組，整理成堆這樣的結構，即轉成完全二叉樹并且使用堆的形式來存儲，滿足下标關系，并且滿足堆（大堆/小堆特點）的關系
• 可以使用向上調整/向下調整實作
• 1）向下調整

  

  如上圖所示：0的左右子樹都是大堆，此時可以進行向下調整

  調整過程：

  .從待調整的位置出發，取出該接待您的左右子樹（通過下标換算方式）

  .該例是大堆，是以找出其左右孩子中的較大值，拿目前節點與該較大值進行比較，看這兩個元素的大小關系是否符合“大堆”的要求，倘若不符合，交換這兩個元素

  .将剛才被交換的位置作為新的起始位置， 再來找兩個子節點的位置，并且找到較大值， 重複上述過程

注意：向下調整建堆時，必須是從後往前循環，從前往後是不行的

因為向下調整的前提條件是左右子樹必須已經滿足堆的要求了，才能向下調整根節點的位置

public class Heap {
    //向下調整(是建立堆的有一個核心操作)
    //前提條件：要求目前被調整節點的左右子樹都已經是堆了
    //參數中傳入數組，數組有效元素長度、待調整的起始位置
    //差別arr.length--->數組總的長度
    //按照大堆方式實作
    // 時間複雜度：O（logN）---(依次*2或者/2，其時間複雜度都與logN有關)
   private static void shiftDown(int[] arr,int size,int index){
        //待調整位置
        int parent=index;
        //待調整位置節點的左子樹
        int child=2*index+1;
        while(child<size) {
            //讓child指向左右子樹值較大者
            if (child + 1 < size && child + 1 > child) {
                child = child+ 1;
            }
            //比較待調整元素和該左子樹的值,如果左子樹節點的值大于待調整位置的值，交換
            if (arr[child] > arr[parent]) {
                int tmp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = tmp;
            } else {
                break;
            }
            //調整之後，更新待調整位置及該位置左子樹的位置,以備下次循環
            parent = child;
            child = 2 * parent + 1;
        }
    }
    //使用向下調整建堆操作
    //時間複雜度O(N)(數學推導出來的)
    public void creatHeap(int[] array)  {
        //基于向下調整建堆
        //（1）從後往前周遊數組，針對每個下标都去向下調整
        for(int i=array.length-1;i>=0;i--){
            shiftDown(array,array.length,i);
        }
        //(2)代碼優化：實際向下調整時，可從第一個非葉子節點進行向下調整(葉子節點沒有向下調整的必要)
        //最後一個非葉子節點即最後一個節點的父節點，下标為(length-1)-1)/2
      for(int i=((array.length-1)-1)/2;i>=0;i--){
            shiftDown(array,array.length,i);
        }
    }
}
           

• 2）向上調整—與元素插入堆操作相關

  調整過程：

  調整的前提是該堆已經符合大堆/小堆要求，将待調整元素與該元素的父節點進行比較，根據大小堆規則進行交換，若還未達到要求，重複上述過程

//二、 向上調整(以大堆為例)
    public void shiftUp(int[] arr,int size,int index){
        //建立一個child引用指向待調整位置
        int child=index;
        //建立一個parent引用指向其父節點的位置
        int parent=(child-1)/2;
        //當child=0時表示已經通路到根節點
        while(child>0){
            //比較待調整位置節點與父節點的大小
            if(arr[child]>arr[parent]){
                int tmp=arr[child];
                arr[child]=arr[parent];
                arr[parent]=tmp;
            }else{
                break;//滿足要求，直接跳出循環
            }
            //更新child與parent，以便下次循環
            child=parent;
            parent=(child-1)/2;
        }
    }
    //使用向上調整(基于offer)的建堆操作
    public  void createHeap1(int[] arr){
        //最開始時，數組為空
        //循環周遊數組，把元素通過offer方法插入數組即可
        for(int x:arr){
            offer(x);
        }

    }

           

3、堆的核心操作—基于"向上調整"和"向下調整"來展開

1）元素插入堆

//往堆中插入元素
    //目前存儲堆的數組
    private int[] arr=new int[100] ;
    private int size=0;
    //該方法需要用到成員變量，是以不加static，通過該方法向存儲堆的數組末尾插入元素
    public void offer(int val){
        //數組滿時,插入失敗（此處不進行擴容操作）
        if(size>arr.length){
            return;
        }
        //尾插
        arr[size]=val;
        size++;

        //尾插完成之後進行向上調整
        shiftUp(arr,size,size-1);
    }
           

2）取堆頂元素

//擷取堆頂元素
    public Integer peek(){
        if(size==0){
            //數組為空
            return null;
        }
        return arr[0];
    }
           

3） 删除堆頂元素

注意：堆元素的删除操作隻能是删除堆頂元素

思路：（移形換影）

将0号的元素，即堆頂元素與最後一個元素交換，然後size–，再将0号元素進行向下調整即可

//删除堆頂元素
    public Integer poll(){
        if(size==0){
            return null;
        }
        //将0号元素與最後一個元素進行交換
        int result=arr[0];
        int tmp=arr[0];
        arr[0]=arr[size-1];
        arr[size-1]=tmp;
        size--;
        //從0号元素開始，往下進行向下調整
        shiftDown(arr,size,0);
        return result;
    }