堆(Heap)的基本概念 堆是一種完全二叉樹(Complete Binary Tree),其性質使得堆可以高效地支持以下操作: 插入(Insert):將一個新元素加入到堆中。 刪除最大/最小元素(Delete Max/Min):移除並返回堆中的最大(大根堆)或最小(小根堆)元素。 獲取最大/最小元素 ...
堆(Heap)的基本概念
堆是一種完全二叉樹(Complete Binary Tree),其性質使得堆可以高效地支持以下操作:
- 插入(Insert):將一個新元素加入到堆中。
- 刪除最大/最小元素(Delete Max/Min):移除並返回堆中的最大(大根堆)或最小(小根堆)元素。
- 獲取最大/最小元素(Get Max/Min):返回堆中的最大(大根堆)或最小(小根堆)元素。
大根堆(Max-Heap)
特性:
- 每個節點的值都大於或等於其子節點的值。
- 根節點是堆中最大的元素。
插入操作:
- 將新元素插入到樹的最底層的最後位置(保持完全二叉樹的性質)。
- 進行“上浮”操作,將新元素逐步與其父節點交換,直到堆的性質恢復或到達根節點為止。
刪除最大元素:
- 移除根節點。
- 將最後一個元素移動到根位置。
- 進行“下沉”操作,將根節點逐步與其較大的子節點交換,直到堆的性質恢復或到達葉子節點為止。
小根堆(Min-Heap)
特性:
- 每個節點的值都小於或等於其子節點的值。
- 根節點是堆中最小的元素。
插入操作:
- 將新元素插入到樹的最底層的最後位置(保持完全二叉樹的性質)。
- 進行“上浮”操作,將新元素逐步與其父節點交換,直到堆的性質恢復或到達根節點為止。
刪除最小元素:
- 移除根節點。
- 將最後一個元素移動到根位置。
- 進行“下沉”操作,將根節點逐步與其較小的子節點交換,直到堆的性質恢復或到達葉子節點為止。
C++ 示例代碼
以下是詳細的 C++ 示例代碼,展示如何實現大根堆和小根堆:
#include <iostream>
//在c++中,使用優先隊列需要包含queue這個頭文件
#include <queue>
#include <vector>
// 大根堆(預設行為)
void maxHeapExample() {
// 創建一個大根堆
std::priority_queue<int> maxHeap;
// 插入元素
maxHeap.push(10);
maxHeap.push(20);
maxHeap.push(5);
maxHeap.push(15);
std::cout << "Max-Heap (大根堆): ";
// 輸出並刪除堆頂元素
while (!maxHeap.empty()) {
std::cout << maxHeap.top() << " "; // 獲取堆頂元素
maxHeap.pop(); // 刪除堆頂元素
}
std::cout << std::endl;
}
// 小根堆
void minHeapExample() {
// 自定義比較函數,逆序(大根堆),實現小根堆
auto cmp = [](int left, int right) { return left > right; };
std::priority_queue<int, std::vector<int>, decltype(cmp)> minHeap(cmp);
// 插入元素
minHeap.push(10);
minHeap.push(20);
minHeap.push(5);
minHeap.push(15);
std::cout << "Min-Heap (小根堆): ";
// 輸出並刪除堆頂元素
while (!minHeap.empty()) {
std::cout << minHeap.top() << " "; // 獲取堆頂元素
minHeap.pop(); // 刪除堆頂元素
}
std::cout << std::endl;
}
int main() {
maxHeapExample();
minHeapExample();
return 0;
}
代碼解釋
- 大根堆(Max-Heap):
std::priority_queue<int>
預設是大根堆。priority_queue
是 STL 提供的容器適配器,基於堆實現。- 插入元素使用
push()
,獲取堆頂元素使用top()
,刪除堆頂元素使用pop()
。
- 小根堆(Min-Heap):
- 通過自定義比較函數來實現小根堆。
std::priority_queue
的構造函數允許傳遞自定義的比較函數。 auto cmp = [](int left, int right) { return left > right; };
是一個 lambda 表達式,用於將小根堆的比較函數定義為left > right
。- 構造
priority_queue
時,傳遞cmp
作為比較函數,這樣就會形成小根堆。
- 通過自定義比較函數來實現小根堆。
小根堆的實現細節與第二種實現方式
在 C++ 的 priority_queue
中,如果你不顯式地提供第二個模板參數(即底層容器類型),它會預設使用 std::vector
作為底層容器。這意味著,你可以只指定元素類型和比較函數(或者不指定比較函數,使用預設的比較方式),而不必顯式地指定底層容器類型。
示例:
#include <iostream>
#include <queue>
struct Compare {
bool operator()(int left, int right) {
// 小根堆的比較規則:左邊的值小於右邊的值返回 true
return left > right;
}
};
void minHeapExample() {
// 不顯式指定底層容器類型,仍然會使用預設的 std::vector<int>
std::priority_queue<int, std::vector<int>, Compare> minHeap;
// 插入元素
minHeap.push(10);
minHeap.push(20);
minHeap.push(5);
minHeap.push(15);
std::cout << "Min-Heap (小根堆): ";
// 輸出並刪除堆頂元素
while (!minHeap.empty()) {
std::cout << minHeap.top() << " "; // 獲取堆頂元素
minHeap.pop(); // 刪除堆頂元素
}
std::cout << std::endl;
}
int main() {
minHeapExample();
return 0;
}
解釋:
- 在
std::priority_queue<int, std::vector<int>, Compare> minHeap;
中,我們沒有顯式地提供第二個模板參數(底層容器類型),因此預設使用std::vector<int>
。 - 這樣做的好處是簡化了代碼,使其更具可讀性,並且仍然能夠正常使用小根堆的功能。
- 如果你想要使用除了
std::vector
以外的其他底層容器,你可以顯式地指定第二個模板參數,例如std::deque<int>
或者其他適合的容器類型。
因此,答案是:可以不顯式提供第二個模板參數 std::vector<int>
,priority_queue
能夠識別到並使用預設的 std::vector
作為底層容器類型。
比較規則的解釋
在 C++ 的 priority_queue
中,如果我們想要實現一個小根堆(Min Heap),是使用 left > right
的比較規則。
比較規則解釋:
-
小根堆(Min Heap):
- 在小根堆中,父節點的值應該小於或等於每個子節點的值。
- 因此,在 C++ 的
priority_queue
中,應該使用比較函數或者仿函數,確保left
比right
大,即left > right
。
-
大根堆(Max Heap):
- 在大根堆中,父節點的值應該大於或等於每個子節點的值。
- 因此,比較函數應該返回
left < right
。
示例解釋:
如果要實現一個小根堆,確保堆頂元素是最小的,比較函數應該是這樣定義的:
struct MinHeapComparator {
bool operator()(int left, int right) {
return left > right;
}
};
int main() {
std::priority_queue<int, std::vector<int>, MinHeapComparator> minHeap;
minHeap.push(10);
minHeap.push(2);
minHeap.push(1);
minHeap.push(4);
minHeap.push(13);
while (!minHeap.empty()) {
int t = minHeap.top();
minHeap.pop();
std::cout << t << " ";
}
return 0;
}
在這個示例中,MinHeapComparator
是一個仿函數,它實現了小根堆的比較規則 left > right
,確保了堆頂的元素是最小的。
總結:
對於小根堆的實現,確實應該使用 left > right
的比較規則。這個比較規則確保了在堆中,父節點的值小於或等於每個子節點的值,從而滿足小根堆的特性。