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

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

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

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

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

基本用法示例：

#include
#include iostream>
using namespace std;

// 默认是大顶堆（最大值在顶部）
std::priority_queue pq;
pq.push(10);
pq.push(30);
pq.push(20);
cout pq.pop();
cout

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

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

// 使用 greater 比较器
std::priority_queue, greater> min_pq;
min_pq.push(30);
min_pq.push(10);
min_pq.push(20);
cout

自定义类型比较：

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

有道翻译AI助手

有道翻译提供即时免费的中文、英语、日语、韩语、法语、德语、俄语、西班牙语、葡萄牙语、越南语、印尼语、意大利语、荷兰语、泰语全文翻译、网页翻译、文档翻译、PDF翻

下载

struct Task {
   int priority;
   string name;
};

// 自定义比较结构体
struct Compare {
   bool operator()(const Task& a, const Task& b) {
      return a.priority    }
};

std::priority_queue, Compare> task_queue;

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

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

#include
#include stream>
using namespace std;

class MaxPriorityQueue {
private:
   vector heap;

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

   // 向下调整（删除后）
   void heapifyDown(int index) {
      int left, right, largest;
      while ((left = 2 * index + 1)          largest = left;
         right = left + 1;
         if (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.pop();
cout

常见应用场景

优先队列常用于：

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

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