我是一個計算機專業研0的學生卡蒙Camel🐫🐫🐫（剛保研）
記錄每天學習過程（主要學習Java、python、人工智能），總結知識點（內容來自：自我總結+網上借鑒）
希望大家能一起發現問題和補充，也歡迎討論👏👏👏

堆

堆的介紹

堆是一種特殊的樹形數據結構，通常以完全二叉樹的形式表示，并且滿足堆屬性。根據堆屬性的不同，堆可以分為兩種類型：

• 最大堆（Max Heap）：對于每個節點，它的值都大于或等于其子節點的值。因此，堆頂元素（根節點）總是最大的。
• 最小堆（Min Heap）：對于每個節點，它的值都小于或等于其子節點的值。因此，堆頂元素（根節點）總是最小的。

堆存儲

• （二叉）堆可以用完全二叉樹的形式進行存儲。
• 樹中任意節點 i，其左子節點序號為 2*i，右子節點序號為 2*i+1

堆操作

堆插入

1. 將要插入的元素放到最后
2. 從底向上，如果父結點比該元素小，則該節點和父結點交換，直到無法交換

刪除堆頂

刪除對頂元素是最大堆(最小堆)的最大值(最小值)，為了保持堆的性質，需要對堆的結構進行調整，我們將這個過程稱之為"堆化"，有兩種方法：

1. 自底向上的堆化
2. 自頂向下堆化

自底向上堆化

以大頂堆為例：

1. 先刪除堆頂元素(即數組中index = 1的位置)
2. 比較根結點的左子節點和右子節點(index = 2和3)，較大的元素放到根節點
3. 此時又有空位，和步驟2一樣，空位兩個子節點較大的移動到空位，直到最底部

自頂向下堆化

1. 我們將最后一個元素移動到堆頂。
2. 不停與左右子節點的值進行比較，和較大的子節點交換位置，直到無法交換位置。

堆排序

堆排序分為兩個步驟：

1. 建堆
2. 排序

1. 建堆

建堆需要對所有非葉節點的自頂向下堆化。

順序是從index=n/2到index=1依次進行堆化

引用JavaGuide的圖：

1. 一開始沒排序前的數組（n = 6， 所以要從索引為 3 到 1 的順序進行堆化）：

2. 對index=3的節點進行堆化：

3. 對index=2的節點進行堆化

4. 對index=1的節點進行堆化，堆化完成

2. 排序

我們在第一步已經建堆完畢，故堆頂元素就是最大值。所以我們重復取出堆頂元素，將這個最大的堆頂元素放至數組末尾，并對剩下的元素進行堆化即可。

1. 取出堆頂元素并且堆化

2. 一次取出堆頂并且優化