c++中如何实现优先队列_c++优先队列实现方法

答案：C++中优先队列可通过std::priority_queue使用或手动实现堆。默认为大顶堆，可用greater创建小顶堆，支持自定义比较；手动实现需维护堆结构，常见于算法场景如Dijkstra和Huffman编码。

在C++中，优先队列（priority queue）可以通过标准库中的 std::priority_queue 容器适配器直接使用，也可以通过底层数据结构（如堆）手动实现。下面分别介绍这两种方式。

使用 std::priority_queue（推荐方式）

C++ 标准库提供了 std::priority_queue，它基于堆实现，默认是一个大顶堆（最大值优先）。

基本用法示例：

#include <queue>
#include <iostream>
using namespace std;

// 默认是大顶堆（最大值在顶部）
std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
cout << pq.top() << endl; // 输出 30
pq.pop();
cout << pq.top() << endl; // 输出 20

创建小顶堆（最小值优先）：

立即学习“C++免费学习笔记（深入）”；

// 使用 greater 比较器
std::priority_queue<int, vector<int>, greater<int>> min_pq;
min_pq.push(30);
min_pq.push(10);
min_pq.push(20);
cout << min_pq.top() << endl; // 输出 10

自定义类型比较：

比如处理结构体或类时，可以重载比较函数。

先见AI

数据为基，先见未见

95

查看详情

struct Task {
   int priority;
   string name;
};

// 自定义比较结构体
struct Compare {
   bool operator()(const Task& a, const Task& b) {
      return a.priority < b.priority; // 大顶堆：优先级高的在前
   }
};

std::priority_queue<Task, vector<Task>, Compare> task_queue;

手动实现优先队列（基于堆）

如果不使用STL，可以用数组和堆的性质自己实现一个简单的优先队列。以下是一个简化的大顶堆实现。

#include <vector>
#include <iostream>
using namespace std;

class MaxPriorityQueue {
private:
   vector<int> heap;

   // 向上调整（插入后）
   void heapifyUp(int index) {
      while (index > 0) {
         int parent = (index - 1) / 2;
         if (heap[index] <= heap[parent]) break;
         swap(heap[index], heap[parent]);
         index = parent;
      }
   }

   // 向下调整（删除后）
   void heapifyDown(int index) {
      int left, right, largest;
      while ((left = 2 * index + 1) < heap.size()) {
         largest = left;
         right = left + 1;
         if (right < heap.size() && heap[right] > heap[left])
            largest = right;
         if (heap[index] >= heap[largest]) break;
         swap(heap[index], heap[largest]);
         index = largest;
      }
   }

public:
   void push(int value) {
      heap.push_back(value);
      heapifyUp(heap.size() - 1);
   }

   void pop() {
      if (empty()) return;
      swap(heap[0], heap.back());
      heap.pop_back();
      heapifyDown(0);
   }

   int top() { return heap[0]; }

   bool empty() { return heap.empty(); }
};

使用示例：

MaxPriorityQueue pq;
pq.push(10);
pq.push(30);
pq.push(20);
cout << pq.top() << endl; // 输出 30
pq.pop();
cout << pq.top() << endl; // 输出 20

常见应用场景

优先队列常用于：

• 堆排序
• Dijkstra 最短路径算法
• Huffman 编码
• 合并多个有序链表
• 实时任务调度系统

基本上就这些。日常开发建议直接使用 std::priority_queue，效率高且不易出错。需要自定义逻辑时再考虑手动实现。

以上就是c++++中如何实现优先队列_c++优先队列实现方法的详细内容，更多请关注php中文网其它相关文章！