堆（Heap）的原理與C++實現

1. 什么是堆？

堆（Heap）是一種特殊的樹形數據結構，通常用于實現優先隊列。堆可以分為兩種類型：

最大堆（Max Heap）：每個節點的值都大于或等于其子節點的值。
最小堆（Min Heap）：每個節點的值都小于或等于其子節點的值。

堆通常是一個完全二叉樹，這意味著除了最后一層，其他層都是完全填滿的，并且最后一層的節點都盡可能地靠左排列。

2. 堆的性質

完全二叉樹：堆是一個完全二叉樹，這意味著它可以用數組來高效地表示。
堆序性質：在最大堆中，父節點的值總是大于或等于其子節點的值；在最小堆中，父節點的值總是小于或等于其子節點的值。

Tips: 堆是`完全二叉樹`，并非`二叉搜索樹`

在數據結構中，完全二叉樹和二叉搜索樹是兩種常見的樹形結構，它們雖然都屬于二叉樹的范疇，但在定義、性質和應用場景上有顯著的區別。下面我們將詳細分析它們的區別。

特性	完全二叉樹	二叉搜索樹
定義	節點從上到下、從左到右依次填充	左子樹 < 根節點 < 右子樹
有序性	不一定有序	中序遍歷結果有序
結構要求	必須是完全填充的（最后一層靠左）	無特殊結構要求，只需滿足有序性
查找效率	不支持高效查找	支持高效查找（平衡時 O(log n)）
插入和刪除	通常用于堆操作，不支持動態插入刪除	支持動態插入和刪除
應用場景	堆、優先隊列	查找、排序、數據庫索引
數組表示	可以用數組高效表示	通常用指針或引用表示

完全二叉樹示例

        10/  \5    15/ \   /2   7 12

節點從上到下、從左到右依次填充。
最后一層的節點靠左排列。

二叉搜索樹示例

        10/  \5    15/ \   / \2   7 12 20

左子樹的所有節點值小于根節點，右子樹的所有節點值大于根節點。
中序遍歷結果為 [2, 5, 7, 10, 12, 15, 20]，是一個有序序列。

3. 堆的操作

堆的主要操作包括：

插入（Insert）：將一個新元素插入堆中，并保持堆的性質。
刪除（Delete）：刪除元素，并保持堆的性質。
查詢（Query）：查詢堆頂元素
構建堆（Build Heap）：將一個無序數組構建成一個堆。

4. 堆的實現

堆通常使用數組來實現。在從數組下標0開始存儲的堆，對于一個索引為 i 的節點：

其父節點的索引為 (i - 1) / 2
其左子節點的索引為 2 * i + 1
其右子節點的索引為 2 * i + 2

4.1 堆的性質維護

堆的插入過程

假設我們有一個最大堆，初始堆為：[100, 19, 36, 17, 3, 25, 1, 2, 7]，其對應的完全二叉樹結構如下（用數組表示）：

        100/     \19       36/  \     /  \17   3   25   1/ \
2  7

插入一個新元素40
將新元素添加到堆的末尾：堆的數組表示為 [100, 19, 36, 17, 3, 25, 1, 2, 7, 40]，對應的完全二叉樹結構如下：

     100/      \19      36/   \    / \17    3  25  1
/ \    /
2  7  40

向上調整（上浮）：從新插入的節點開始，與其父節點比較。如果當前節點的值大于父節點的值，則交換它們的位置。

40 的父節點是 3，40 > 3，交換它們的位置：

        100/      \19       36/  \     /  \17   40  25   1/ \   /2  7  3

40 的新父節點是 19，40 > 19，交換它們的位置：

      100/      \40       36/  \     /  \
17   19  25   1
/ \   /
2  7 3

40 的新父節點是 100，40 < 100，停止調整。
最終，插入 40 后的堆為：[100, 40, 36, 17, 19, 25, 1, 2, 7, 3]。

總結:堆在插入元素后，需要進行上浮（up）操作，是不斷與父節點比較，若父節點小于當前節點，則交換位置。具體代碼實現示例如下：

//存儲下標從1開始，以大根堆為例
void heap_up(int idx){while(idx != 1){int parent = idx >> 1;if(heap[parent] < heap[idx]){swap(heap[parent], heap[idx]);idx = parent;}else{break;}}
}

堆的刪除過程

假設我們從上述堆中刪除最大值（堆頂元素 100）。

將堆頂元素與最后一個元素交換：交換 100 和 3 的位置，得到 [3, 40, 36, 17, 19, 25, 1, 2, 7, 100]，然后刪除最后一個元素（100），得到 [3, 40, 36, 17, 19, 25, 1, 2, 7]。這是因為我們在用數組存儲堆的時候，頭部元素的刪除面臨整個數組的移動，相當消耗計算資源，于是我們選擇將頭部元素和尾部元素進行交換，進行刪除尾部，再調整堆
向下調整（下沉）：從堆頂開始，比較當前節點與其子節點的值，將當前節點與較大的子節點交換，直到滿足堆的性質。

當前堆頂是 3，其子節點是 40 和 36，40 > 36，選擇 40 與 3 交換得到：

      40/      \3       36/  \     /  \
17   19  25   1
/ \  
2  7

3 的新位置是左子樹的根，其子節點是 17 和 19，19 > 17，選擇 19 與 3 交換：

      40/      \19       36/  \     /  \
17   3  25   1
/ \  
2  7

最終，刪除 100 后的堆為：[40, 19, 36, 17, 3, 25, 1, 2, 7]。

void heap_down(int idx){int size = top;while(1){int leftChild = idx * 2;int rightChild = idx * 2 + 1;int largest = idx;if(leftChild < size && heap[largest] < heap[leftChild]){largest = leftChild;}if(rightChild < size && heap[largest] < heap[rightChild]){largest = rightChild;}if (largest != idx) {swap(heap[idx], heap[largest]);idx = largest;} else {break;}}
}

4.2 C++ 實現最大堆

這里展示一個封裝成對象的大根堆

#include <iostream>
#include <vector>
#include <algorithm>class MaxHeap {
private:std::vector<int> heap;void heapifyUp(int index) {while (index > 0) {int parentIndex = (index - 1) / 2;if (heap[index] > heap[parentIndex]) {std::swap(heap[index], heap[parentIndex]);index = parentIndex;} else {break;}}}void heapifyDown(int index) {int size = heap.size();while (true) {int leftChild = 2 * index + 1;int rightChild = 2 * index + 2;int largest = index;if (leftChild < size && heap[leftChild] > heap[largest]) {largest = leftChild;}if (rightChild < size && heap[rightChild] > heap[largest]) {largest = rightChild;}if (largest != index) {std::swap(heap[index], heap[largest]);index = largest;} else {break;}}}public:void insert(int value) {heap.push_back(value);heapifyUp(heap.size() - 1);}int extractMax() {if (heap.empty()) {throw std::out_of_range("Heap is empty");}int maxValue = heap[0];heap[0] = heap.back();heap.pop_back();heapifyDown(0);return maxValue;}void buildHeap(const std::vector<int>& array) {heap = array;for (int i = (heap.size() / 2) - 1; i >= 0; --i) {heapifyDown(i);}}void printHeap() const {for (int value : heap) {std::cout << value << " ";}std::cout << std::endl;}
};int main() {MaxHeap maxHeap;maxHeap.insert(10);maxHeap.insert(20);maxHeap.insert(15);maxHeap.insert(30);maxHeap.insert(40);std::cout << "Max Heap: ";maxHeap.printHeap();std::cout << "Extracted Max: " << maxHeap.extractMax() << std::endl;std::cout << "Max Heap after extraction: ";maxHeap.printHeap();std::vector<int> array = {5, 3, 8, 1, 9};maxHeap.buildHeap(array);std::cout << "Max Heap built from array: ";maxHeap.printHeap();return 0;
}

4.2 代碼解析

heapifyUp：用于在插入新元素后，從下往上調整堆，確保堆的性質。
heapifyDown：用于在刪除堆頂元素后，從上往下調整堆，確保堆的性質。
insert：將新元素插入堆中，并調用 heapifyUp 進行調整。
extractMax：刪除并返回堆頂元素，然后調用 heapifyDown 進行調整。
buildHeap：將一個無序數組構建成一個堆。

5. 堆的應用

優先隊列：堆是實現優先隊列的理想數據結構，因為可以快速獲取和刪除最大或最小元素。
堆排序：堆排序是一種基于堆的比較排序算法，時間復雜度為 O(n log n)。
Dijkstra算法：在圖的單源最短路徑算法中，堆用于高效地選擇下一個要處理的節點。

6. 總結

堆是一種非常高效的數據結構，特別適用于需要頻繁獲取最大或最小元素的場景。通過數組實現堆，可以充分利用其完全二叉樹的性質，使得插入、刪除和構建堆的操作都能在 O(log n) 的時間內完成。

7.練習

ACWing模擬堆
這個題相較普通的堆，增添了一個需要維護的對象，就是這個數字是第幾次插入的。所以我們需要額外維護兩個數組pos和inv_pos，分別表示第k個插入的數在堆數組中的索引，和堆數組中第i個數是第幾個插入的，完整代碼如下：

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int maxn = 1e5 + 7;
int heap[maxn], top;
int pos[maxn], inv_pos[maxn];
void heap_swap(int a, int b){swap(heap[a], heap[b]);swap(pos[inv_pos[a]], pos[inv_pos[b]]);swap(inv_pos[a], inv_pos[b]);
}
void down(int idx){while(1){int leftChild = idx * 2;int rightChild = idx * 2 + 1;int smallest = idx;if(leftChild <= top && heap[leftChild] < heap[smallest])smallest = leftChild;if(rightChild <= top && heap[rightChild] < heap[smallest])smallest = rightChild;if(idx != smallest) {heap_swap(idx, smallest);idx = smallest;}elsebreak;}
}
void up(int idx){while(idx != 1){int parent = idx >> 1;if(heap[parent] > heap[idx]){heap_swap(idx, parent);idx = parent;}else{break;}}
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;string op;int x, k, cnt = 0;while(n--){cin>>op;if(op == "I"){cin>>x;heap[++top] = x;pos[++cnt] = top;inv_pos[top] = cnt;up(top);}else if(op == "PM"){cout<<heap[1]<<endl;}else if(op == "DM"){heap_swap(1, top);top--;down(1);}else if(op == "D"){cin>>k;int now = pos[k];heap_swap(now, top);top --;down(now);up(now);}else if(op == "C"){cin>>k>>x;heap[pos[k]] = x;up(pos[k]);down(pos[k]);}}return 0;
}