c++优先队列代码模板

// 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++中，可以使用STL库中的priority_queue来实现优先队列。

下面是一个简单的C++代码示例，演示了如何使用优先队列实现一个最大堆：

#include <iostream>
#include <queue>

int main() {
    // 创建一个优先队列，默认为最大堆
    std::priority_queue<int> pq;

    // 向优先队列中插入元素
    pq.push(10);
    pq.push(30);
    pq.push(20);

    // 访问队列中的最大元素
    std::cout << "队列中的最大元素为：" << pq.top() << std::endl;

    // 弹出队列中的最大元素
    pq.pop();

    // 再次访问队列中的最大元素
    std::cout << "弹出一个元素后，队列中的最大元素为：" << pq.top() << std::endl;

    return 0;
}

在上面的代码中，我们首先包含了`<iostream>`和`<queue>`头文件，分别用于输入输出和使用优先队列。然后，我们创建了一个`std::priority_queue<int>`对象`pq`，默认为最大堆。

接下来，我们使用`push()`函数向优先队列中插入元素。然后，使用`top()`函数访问队列中的最大元素，并使用`pop()`函数弹出队列中的最大元素。

注意，优先队列默认是按照元素的大小进行排序的，对于基本数据类型，按照从大到小的顺序排列。如果要实现最小堆，可以使用`std::greater`作为第二个模板参数，例如`std::priority_queue<int, std::vector<int>, std::greater<int>>`。