📢博客主頁：🏀敲代碼的布萊恩特🏀
📢歡迎點贊 👍 收藏 ?留言 📝 歡迎討論！👏
📢本文由 【敲代碼的布萊恩特】 原創，首發于 CSDN🙉🙉🙉
📢由于博主是在學小白一枚，難免會有錯誤，有任何問題歡迎評論區留言指出，感激不盡！?
📖精品專欄（不定時更新）【JavaSE】 【Java資料結構】【LeetCode】

🎄1.二叉樹的順序儲存

🛸二叉樹的順序儲存

• 使用陣列保存二叉樹結構，方式即將二叉樹用層序遍歷方式放入陣列中，陣列的下標位置與二叉樹節點位置是一 一對應的，

• 一般只適合表示完全二叉樹，因為非完全二叉樹會有空間的浪費，

• 這種方式的主要用法就是堆的表示，
  

🛸下標關系

• 已知雙親(parent)的下標，則：
  左孩子(left)下標 = 2 * parent + 1;
  右孩子(right)下標 = 2 * parent + 2;
• 已知孩子（不區分左右）(child)下標，則：
  雙親(parent)下標 = (child - 1) / 2;
  

🎄2.堆

🛸概念

1. 堆 邏輯上是一棵完全二叉樹
2. 堆 物理上是保存在陣列中
3. 滿足任意結點的值都大于其子樹中結點的值，叫做大堆，或者大根堆，或者最大堆
4. 反之，則是小堆，或者小根堆，或者最小堆
5. 堆的基本作用是，快速找集合中的最值

🛸操作——向下調整（以大根堆為例，小根堆就是換個符號的事）

前提：
左右子樹必須已經是一個堆，才能調整，

說明：

1. elem 代表存盤堆的陣列
2. length 代表陣列中被視為堆資料的個數（即陣列有效元素個數）
3. parent 代表要調整子樹根節點位置的下標
4. child 代表最小值孩子下標（如果左右都有孩子，先比較，然后使child代表最小值孩子下標）

向下調整的程序：

1. parent 如果已經是葉子結點，則整個調整程序結束
2. 判斷 parent 位置有沒有孩子
3. 因為堆是完全二叉樹，沒有左孩子就一定沒有右孩子，所以先判斷是否有左孩子
4. 因為堆的存盤結構是陣列，所以判斷是否有左孩子，即判斷左孩子下標是否越界，即 若(parent×2+1) >= size 越界，再判斷是否有右孩子，即若(parent×2+2) >= size 越界
5. 確定最小孩子，比較孩子節點值，child最后儲存的一定是最小孩子的下標
   ① 如果右孩子不存在，則 child = parent×2+1
   ② 否則，比較 elem[parent×2+1] 和 elem[parent×2+2] 值的大小，child儲存值小的孩子的下標
6. 比較 elem[parent] 的值 和 elem[child] 的值，如果elem[parent] <= elem[child]，則滿足堆的性質，調整結束
7. 否則，交換 elem[parent] 和 elem[child]的值
8. 然后更新 parent 和 child 下標，即parent = child; child = 2 * parent + 1;向下重復以上程序
   

實作代碼：

//向下調整
    public void adjustDown(int parent,int length){
        int child = parent*2+1;//先找到左孩子節點
        while(child<length) {//當child>=length的時候說明當前子樹已經調整好了
            //先根據左孩子節點判斷右孩子節點是否存在，且是否大于左孩子節點
            if (child + 1 < length && elem[child + 1] > elem[child]) {//如果存在,且值大于左孩子節點
                child++;
            }
            //保證，child下標的資料  一定是左右孩子的最大值的下標
            if (elem[child] > elem[parent]) {//如果孩子節點最大值，大于父節點，則要交換位置，因為要建大根堆
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                //繼續向下看是否符合大根堆的條件
                parent = child;//更新parent下標
                child = 2 * parent + 1;//更新child下標
            }else{//否則不用換位置
                break;
            }
        }
    }

🛸操作——建堆

下面我們給出一個陣列，這個陣列邏輯上可以看做一顆完全二叉樹，但是還不是一個堆，現在我們通過演算法，把它構建成一個堆，
根節點左右子樹不是堆，我們怎么調整呢？這就用到上邊說的向下調整

• 借助向下調整，就可以把一個陣列構建成堆，
• 從倒數第一個非葉子節點開始，從后往前遍歷陣列，針對每個位置，依次向下調整即可，

調整前

int[] array = { 1，2，3，4，5，6，7，8，9，10 };

調整后

int[] array = { 10，9，7，8，5，6，3，1，4，2 };

實作代碼：

//建大堆
    public void createHeap(int array[]){
        //將傳入的陣列值存入堆的陣列中
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }
        //從下往上建堆，parent 就代表每顆子樹的根節點
        for (int parent=(array.length-1-1)/2 ; parent>=0 ; parent--){
            //對每個子樹進行向下調整
            //第二個引數傳入有效元素個數是因為
            //每次調整的結束位置應該是：this.usedSize.
            adjustDown(parent,this.usedSize);
        }
    }

🎄3.堆的應用——優先級佇列

🛸概念

在很多應用中，我們通常需要按照優先級情況對待處理物件進行處理，比如首先處理優先級最高的物件，然后處理次高的物件，最簡單的一個例子就是，在手機上玩游戲的時候，如果有來電，那么系統應該優先處理打進來的電話，
在這種情況下，我們的資料結構應該提供兩個最基本的操作，一個是回傳最高優先級物件，一個是添加新的物件，這種資料結構就是優先級佇列(Priority Queue)

🛸內部原理

優先級佇列的實作方式有很多，但最常見的是使用堆來構建，

🛸操作——入佇列

程序（以大堆為例）：

1. 首先按尾插方式放入陣列
2. 比較其和其雙親的值的大小，如果雙親的值大，則滿足堆的性質，插入結束
3. 否則，交換其和雙親位置的值，重新進行 2、3 步驟（向上調整）
4. 直到根結點

圖示：

代碼實作：

//入堆操作
    public void offer(int value){
        //先判斷滿沒滿
        if(isFull()){//滿了要擴容
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }

        elem[usedSize] = value;//尾插到陣列里
        usedSize++;//有效值加1
        adjustUp(usedSize-1);//向上調整
    }

    //向上調整
    public void adjustUp(int child){
        int parent = (child-1)/2;
        while(child>0){
            if (elem[child]>elem[parent]){//如果孩子節點大于雙親節點，換位置
               int tmp = elem[parent];
               elem[parent] = elem[child];
               elem[child] = tmp;
               child = parent;//更新孩子節點位置
               parent = (child-1)/2;//更新雙親點位置
            }else{
                break;
            }
        }
    }
    
    //判斷是否滿了
    public boolean isFull(){
        if (usedSize == elem.length) return true;
        else return false;
    }

🛸操作——出佇列

• 為了防止破壞堆的結構，洗掉時并不是直接將堆頂元素洗掉，而是用陣列的最后一個元素替換堆頂元素
• 有效元素個數要減一，這樣就相當于把隊尾（現在隊尾存的是原堆頂元素）除掉了
• 然后通過向下調整方式重新調整成堆

代碼實作：

//出堆操作（出根節點）
    public void poll() {
        if(isEmpty()) {//先判斷是否是空堆
            return;
        }
        int top = elem[0];//為了不破壞堆結構，不能直接刪首元素，要先根尾部元素交換位置
        elem[0] = elem[this.usedSize-1];//陣列頭尾交換
        elem[usedSize-1] = top;//根節點元素已經來到了陣列最后
        usedSize--;//有效值-1，就相當于洗掉陣列尾部元素
        adjustDown(0,usedSize);//重新向下調整，使之重新變為堆
        //（這時候原來的根節點已經不算了，假設原來是10個節點的堆，現在只有9個了，要做的就是將這余下的9個從頭向下調整為堆）
    }
   
   //判斷是否為空堆
    public boolean isEmpty() {
        return this.usedSize == 0;
    }

🛸回傳隊首元素（優先級最高）

回傳堆頂元素即可

//查看隊首元素
    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException("佇列為空");
        }
        return this.elem[0];
    }

🛸Java中的優先級佇列

PriorityQueue implements Queue

🎄4.堆的應用——TopK問題

戳這里，我姥姥都能看懂，講的很詳細.

關鍵記得，找前 K 個最大的，就建 K 個大小的小堆

🎄5.堆的其他應用——堆排序

• 從小到大排序：先建大根堆
• 從大到小排序：先建小根堆

一定是先創建大堆/小堆

• 開始堆排序：
  先交換 后調整 直到 0下標

從小到大排序 原理就是

1. 根節點（當前樹最大值）與隊尾換位置，這樣最大值的位置就確定了，在陣列最后，end表示陣列尾下標

2. 然后end- -，再進行向下調整，使剩下的節點再變成堆，回圈操作，直到end=0了，說明已經排好了

代碼實作：

//堆排序
public void heapSort() {
        int end = this.usedSize-1;
        while(end > 0) {
            int tmp = this.elem[0];
            this.elem[0] =this.elem[end];
            this.elem[end] = tmp;
            adjustDown(0,end);
            end--;
        }
    }

🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
?原創不易，如有錯誤，歡迎評論區留言指出，感激不盡?
? 如果覺得內容不錯，給個三連不過分吧~ ?
? 看到會回訪~ ?
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙