c++ minheap头文件
时间: 2023-09-23 12:09:44 浏览: 72
可以使用 #include <queue> 头文件来使用 STL 中的最小堆(也称为优先队列)。在使用时,需要定义堆中元素的类型,如下所示:
```C++
#include <queue>
using namespace std;
struct Node{
int val;
Node(int x): val(x) {}
};
struct cmp{
bool operator() (Node a, Node b){
return a.val > b.val;
}
};
int main(){
priority_queue<Node, vector<Node>, cmp> minHeap;
// 使用minHeap进行最小堆操作
return 0;
}
```
以上代码使用结构体 Node 作为堆中元素的类型,使用 cmp 结构体重载 () 运算符,定义了一个按照 Node.val 的大小来比较大小的比较器。定义 priority_queue 时,需要指定堆元素类型 Node,使用 vector<Node> 实现底层容器,使用 cmp 作为比较器,实现最小堆的功能。
相关问题
c++dijkstra算法
Dijkstra算法是一种用于解决单源最短路径问题的经典算法,它可以找到从一个顶点到其他所有顶点的最短路径。下面是C++中实现Dijkstra算法的基本步骤:
1. 创建一个距离数组dist[],用于存储从源顶点到其他顶点的最短距离。初始化dist[]数组,将源顶点的距离设置为0,其他顶点的距离设置为无穷大。
2. 创建一个优先队列(最小堆)minHeap,用于选择下一个要访问的顶点。将源顶点加入minHeap,并将其距离设置为0。
3. 循环执行以下步骤,直到minHeap为空:
a. 从minHeap中取出距离最小的顶点u。
b. 遍历u的所有邻接顶点v,计算从源顶点到v的距离newDist。如果newDist小于dist[v],则更新dist[v]为newDist,并将v加入minHeap。
4. 最终,dist[]数组中存储了从源顶点到所有其他顶点的最短距离。
下面是一个简单的C++代码示例:
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
void dijkstra(vector<vector<pair<int, int>>>& graph, int source, vector<int>& dist) {
int n = graph.size();
dist.resize(n, INT_MAX);
dist[source] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
minHeap.push({0, source});
while (!minHeap.empty()) {
int u = minHeap.top().second;
minHeap.pop();
for (auto& neighbor : graph[u]) {
int v = neighbor.first;
int weight = neighbor.second;
int newDist = dist[u] + weight;
if (newDist < dist[v]) {
dist[v] = newDist;
minHeap.push({newDist, v});
}
}
}
}
int main() {
int n = 5; // 顶点数
vector<vector<pair<int, int>>> graph(n);
// 添加边
graph[0].push_back({1, 2});
graph[0].push_back({2, 4});
graph[1].push_back({2, 1});
graph[1].push_back({3, 7});
graph[2].push_back({3, 3});
graph[2].push_back({4, 5});
graph[3].push_back({4, 2});
int source = 0; // 源顶点
vector<int> dist;
dijkstra(graph, source, dist);
// 输出最短路径
for (int i = 0; i < n; i++) {
cout << "Distance from source to vertex " << i << ": " << dist[i] << endl;
}
return 0;
}
```
c++哈夫曼编码例子
以下是C++实现Huffman编码的例子:
```c++
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
// 定义Huffman树节点
struct HuffmanNode {
char ch; // 字符
int freq; // 频率
HuffmanNode* left; // 左子节点
HuffmanNode* right; // 右子节点
HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};
// 定义比较函数,用于最小堆的排序
struct cmp {
bool operator()(HuffmanNode* a, HuffmanNode* b) {
return a->freq > b->freq;
}
};
// 构造Huffman树
HuffmanNode* buildHuffmanTree(unordered_map<char, int>& freqMap) {
priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> minHeap;
for (auto& p : freqMap) {
minHeap.push(new HuffmanNode(p.first, p.second));
}
while (minHeap.size() > 1) {
HuffmanNode* left = minHeap.top();
minHeap.pop();
HuffmanNode* right = minHeap.top();
minHeap.pop();
HuffmanNode* parent = new HuffmanNode('$', left->freq + right->freq);
parent->left = left;
parent->right = right;
minHeap.push(parent);
}
return minHeap.top();
}
// 递归获取Huffman编码
void getHuffmanCode(HuffmanNode* root, string code, unordered_map<char, string>& codeMap) {
if (!root) {
return;
}
if (root->ch != '$') {
codeMap[root->ch] = code;
}
getHuffmanCode(root->left, code + "0", codeMap);
getHuffmanCode(root->right, code + "1", codeMap);
}
// 打印Huffman编码
void printHuffmanCode(unordered_map<char, string>& codeMap) {
for (auto& p : codeMap) {
cout << p.first << " " << p.second << endl;
}
}
int main() {
unordered_map<char, int> freqMap = {{'a', 45}, {'b', 13}, {'c', 12}, {'d', 16}, {'e', 9}, {'f', 5}};
HuffmanNode* root = buildHuffmanTree(freqMap);
unordered_map<char, string> codeMap;
getHuffmanCode(root, "", codeMap);
printHuffmanCode(codeMap);
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)