c++优先队列代码模板
时间: 2023-05-27 14:01:11 浏览: 57
// C++ code
#include <iostream>
#include <queue>
using namespace std;
int main() {
// 定义一个小根堆
priority_queue<int, vector<int>, greater<int>> pq;
// 元素入队
pq.push(2);
pq.push(4);
pq.push(1);
pq.push(5);
// 查看队首元素
cout << pq.top() << '\n'; // 输出 1
// 弹出队首元素
pq.pop();
// 再次查看队首元素
cout << pq.top() << '\n'; // 输出 2
return 0;
}
相关问题
c++优先队列大根堆代码模板
// 定义一个大根堆类
class MaxHeap {
private:
vector<int> heap; // 使用 vector 存储堆
int size; // 堆的大小
// 工具函数 —— 交换堆中的两个元素
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// 工具函数 —— 堆化某一个节点
void heapify(int index) {
int largest = index; // 先将当前节点标记为最大值
int left = index * 2 + 1; // 左孩子节点的索引
int right = index * 2 + 2; // 右孩子节点的索引
// 比较当前节点、左孩子节点和右孩子节点中的最大值
if (left < size && heap[left] > heap[largest]) {
largest = left;
}
if (right < size && heap[right] > heap[largest]) {
largest = right;
}
// 如果当前节点的值不是最大值,则将当前节点和最大值节点交换,并递归地对最大值节点进行堆化
if (largest != index) {
swap(heap[index], heap[largest]);
heapify(largest);
}
}
public:
// 构造函数 —— 建立一个空堆
MaxHeap() {
size = 0;
}
// 获取堆中元素的数量
int getSize() {
return size;
}
// 判断堆是否为空
bool isEmpty() {
return size == 0;
}
// 在堆末尾添加一个元素,并将其上移对其进行调整
void add(int element) {
heap.push_back(element);
size++;
int index = size - 1;
int parent = (index - 1) / 2;
while (index > 0 && heap[index] > heap[parent]) {
swap(heap[index], heap[parent]);
index = parent;
parent = (index - 1) / 2;
}
}
// 获取堆顶元素
int peek() {
if (size == 0) {
throw "Heap is empty.";
}
return heap[0];
}
// 删除堆顶元素,并将堆末尾的元素放到堆顶,然后将其下沉进行调整
int remove() {
if (size == 0) {
throw "Heap is empty.";
}
int root = heap[0];
heap[0] = heap[size - 1];
size--;
heap.pop_back();
heapify(0);
return root;
}
};
c++优先队列升序实例
C++中的优先队列是一种特殊的队列,它可以根据元素的优先级进行自动排序。在优先队列中,元素按照一定的规则进行排序,每次取出的元素都是优先级最高的。
下面是一个C++优先队列升序实例的代码:
```cpp
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
pq.push(5);
pq.push(2);
pq.push(10);
pq.push(1);
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
return 0;
}
```
在这个例子中,我们使用了`std::priority_queue`来创建一个优先队列。通过指定第二个模板参数为`std::vector<int>`,我们使用了默认的容器类型`std::vector`来存储元素。通过指定第三个模板参数为`std::greater<int>`,我们定义了一个比较函数,使得元素按照升序排列。
在主函数中,我们依次将元素5、2、10、1插入到优先队列中。然后,我们使用`top()`函数获取优先队列中的最小元素,并使用`pop()`函数将其移除。最后,我们输出排序后的结果。