当前位置： 首页 > news >正文

【C++】 priority_queue 容器模拟实现解析

news 2025/9/6 19:26:36

一、仿函数（Functor）：比较策略的封装

仿函数是重载了()运算符的类 / 结构体，可像函数一样被调用。在 priority_queue 中，仿函数用于定义元素的比较规则，实现大顶堆 / 小顶堆的灵活切换。

// 仿函数：小于比较（用于大顶堆，默认）
template<class T>
struct less
{bool operator()(const T& left, const T& right) const{return left < right;  // 左 < 右时返回true}
};// 仿函数：大于比较（用于小顶堆）
template<class T>
struct greater
{bool operator()(const T& left, const T& right) const{return left > right;  // 左 > 右时返回true}
};

解析：

  • 仿函数的核心是operator()，它定义了两个元素的比较逻辑。

  • less<T>：当left < right时返回true，配合堆调整逻辑可实现 “大顶堆”（父节点 > 子节点）。

  • greater<T>：当left > right时返回true，配合堆调整逻辑可实现 “小顶堆”（父节点 < 子节点）。

  • 这种设计采用 “策略模式”，让 priority_queue 无需修改核心代码，仅通过更换仿函数即可切换堆类型。

二、priority_queue 类的核心实现

priority_queue（优先队列）是一种 “适配器容器”，它基于底层容器（默认 vector）实现，内部维护一个 “堆” 结构（完全二叉树），确保每次可高效获取优先级最高的元素（堆顶）。

2.1 模板参数与成员变量
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:// 成员函数声明（见后续）
private:Container _con;  // 底层容器，用于存储堆的元素
};

解析：

  • 模板参数：

    • T：存储的元素类型。

    • Container：底层容器类型（默认 vector），需支持随机访问（如[]操作）和尾部插入 / 删除（push_back/pop_back），因此通常选 vector 或 deque（list 不适合，因不支持随机访问）。

    • Compare：比较仿函数（默认less<T>），决定堆的类型（大顶堆 / 小顶堆）。

  • 成员变量_con：底层容器实际存储元素，堆的结构通过该容器的元素顺序体现（完全二叉树的层次遍历顺序）。

2.2 堆的核心调整算法

堆的核心是 “向上调整” 和 “向下调整”，用于在插入 / 删除元素后维持堆的性质（父节点优先级高于 / 低于子节点）。

2.2.1 向上调整（AdjustUp）

插入元素后，需将新元素从尾部上移到合适位置，确保堆性质。

void AdjustUp(int child)
{Compare com;  // 实例化仿函数，获取比较规则int parent = (child - 1) / 2;  // 计算父节点索引（完全二叉树性质）while (child > 0)  // 子节点索引>0，说明未到根节点{// 若父节点不符合堆规则（需与子节点交换）// 大顶堆：父 < 子 → 交换；小顶堆：父 > 子 → 交换（由com决定）if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);  // 交换父子节点child = parent;  // 子节点上移到父节点位置parent = (child - 1) / 2;  // 重新计算新的父节点}else{break;  // 已满足堆性质，退出循环}}
}

解析：

  • 适用场景：元素插入（push）后调用，新元素初始在容器尾部（child = 最后一个索引）。

  • 核心逻辑：通过(child - 1) / 2计算父节点索引，反复比较父子节点，若父节点不符合规则则交换，直到根节点或满足堆性质。

  • 仿函数作用：com(parent, child)的返回值决定是否需要交换。例如，大顶堆中com是less，当parent < child时返回true，触发交换。

2.2.2 向下调整（AdjustDown）

删除堆顶元素后，需将新的根节点下移到合适位置，维持堆性质。

void AdjustDown(int parent)
{Compare com;  // 实例化仿函数int child = parent * 2 + 1;  // 计算左子节点索引（完全二叉树性质）while (child < _con.size())  // 子节点索引有效（未超出容器范围）{// 找“更需要交换”的子节点（左/右子节点中优先级更高的）// 大顶堆：找更大的子节点；小顶堆：找更小的子节点（由com决定）if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;  // 右子节点更符合交换条件，切换到右子}// 若父节点不符合堆规则（需与子节点交换）if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);  // 交换父子节点parent = child;  // 父节点下移到子节点位置child = parent * 2 + 1;  // 重新计算新的左子节点}else{break;  // 已满足堆性质，退出循环}}
}

解析：

  • 适用场景：堆顶元素删除（pop）后调用，新根节点初始为原最后一个元素（parent = 0）。

  • 核心逻辑：

    • 先通过parent * 2 + 1计算左子节点，比较左 / 右子节点（若右子存在），选择 “更需要交换” 的子节点（由仿函数决定）。

    • 比较父节点与选中的子节点，若不符合规则则交换，反复下移直到叶子节点或满足堆性质。

  • 为什么先比较子节点？确保父节点与 “最优子节点” 交换，一次调整即可维持堆性质。

2.3 优先队列的核心接口
2.3.1 插入元素（push）
void push(const T& x)
{_con.push_back(x);  // 先将元素插入到底层容器尾部AdjustUp(_con.size() - 1);  // 对新插入的元素（尾部）进行向上调整
}

解析：

  • 步骤：先在底层容器尾部添加元素（O (1) 时间，vector 的优势），再通过AdjustUp将其移动到合适位置（O (logn) 时间，n 为元素个数）。

  • 目的：确保插入后仍维持堆的性质。

2.3.2 删除堆顶元素（pop）
void pop()
{if (empty())  // 空队列直接返回return;swap(_con[_con.size() - 1], _con[0]);  // 交换堆顶与最后一个元素_con.pop_back();  // 删除最后一个元素（原堆顶）AdjustDown(0);  // 对新堆顶（原最后一个元素）进行向下调整
}

解析：

  • 步骤：

    • 交换堆顶（索引 0）与最后一个元素（O (1)）；

    • 删除尾部元素（原堆顶，O (1)）；

    • 对新堆顶（原尾部元素）进行向下调整（O (logn)）。

  • 为什么不直接删除堆顶？直接删除会导致底层容器出现 “空洞”，破坏完全二叉树结构，而交换后删除尾部可高效维护结构。

2.3.3 其他基础接口
T& top() { return _con[0]; }  // 获取堆顶元素（优先级最高的元素）
size_t size() { return _con.size(); }  // 返回元素个数
bool empty() { return _con.empty(); }  // 判断队列是否为空

解析：

  • top()：堆顶元素始终在索引 0（完全二叉树的根），直接返回即可（O (1)）。

  • 其他接口直接复用底层容器的功能，简洁高效。

三、测试函数与验证
void priority_queue_test()
{// 1. 大顶堆（默认使用less仿函数）priority_queue<int> max_heap;max_heap.push(8);max_heap.push(18);max_heap.push(3);max_heap.push(6);max_heap.push(10);cout << "大顶堆弹出顺序：";while (!max_heap.empty()){cout << max_heap.top() << " ";  // 输出：18 10 8 6 3max_heap.pop();}cout << endl;// 2. 小顶堆（指定greater仿函数）priority_queue<int, vector<int>, greater<int>> min_heap;min_heap.push(8);min_heap.push(18);min_heap.push(3);min_heap.push(6);min_heap.push(10);cout << "小顶堆弹出顺序：";while (!min_heap.empty()){cout << min_heap.top() << " ";  // 输出：3 6 8 10 18min_heap.pop();}cout << endl;
}

解析：

  • 大顶堆测试：使用默认less仿函数，每次弹出最大元素（18 → 10 → 8 → 6 → 3），符合大顶堆性质。

  • 小顶堆测试：显式指定greater仿函数，每次弹出最小元素（3 → 6 → 8 → 10 → 18），符合小顶堆性质。

  • 测试结果验证了堆调整算法和仿函数的正确性：插入元素后堆结构正确，弹出顺序符合优先级规则。

总结

该实现完整模拟了 C++ 标准库中 priority_queue 的核心功能，其设计特点包括：

  1. 适配器模式：基于底层容器（如 vector）实现，复用容器的存储能力，专注于堆的逻辑维护。

  2. 策略模式：通过仿函数Compare灵活切换比较规则，轻松支持大顶堆 / 小顶堆。

  3. 高效操作：插入（push）和删除（pop）均为 O (logn) 时间复杂度，获取堆顶（top）为 O (1)，适合需要频繁获取最值的场景（如任务调度、贪心算法等）。

理解 priority_queue 的关键在于掌握堆的调整算法（向上 / 向下调整），以及仿函数如何影响堆的性质。

http://www.xdnf.cn/news/1472815.html

相关文章：

  • GDAL 开发起步
  • MySQL抛出的Public Key Retrieval is not allowed
  • nextcyber——暴力破解
  • c++ 压缩与解压缩
  • C++语言编程规范-初始化和类型转换
  • 技术面：Java并发（线程池、ForkJoinPool）
  • Acrobat-2025.001.20643_Win中文_PDF编辑器_便携版安装教程
  • Go初级之十：错误处理与程序健壮性
  • 内存纠错检错方法-SSCDSD
  • vggt代码详解
  • 迁移学习实战：基于 ResNet18 的食物分类
  • BYOFF (Bring Your Own Formatting Function)解析（80）
  • GPU集群扩展：Ray Serve与Celery的技术选型与应用场景分析
  • Pinia 两种写法全解析：Options Store vs Setup Store（含实践与场景对比）
  • (3)Seata AT 模式的事务一致性保证机制
  • MySQL慢查询优化策略
  • 洛谷 P2392 kkksc03考前临时抱佛脚-普及-
  • 【C++题解】贪心和模拟
  • Linux设备down机，如何识别是 断电还是软件复位
  • Java笔记20240726
  • 【Day 22】94.二叉树的中序遍历 104.二叉树的最大深度 226.翻转二叉树 101.对称二叉树
  • linux上nexus安装教程
  • 从“下山”到AI引擎：全面理解梯度下降（下）
  • 学习心得分享
  • 【OJ】C++ vector类OJ题
  • 使用国内镜像源解决 Electron 安装卡在 postinstall 的问题
  • 【Python - 类库 - BeautifulSoup】（01）“BeautifulSoup“使用示例
  • ESP-idf注册双服务器配置
  • SemiSAM+：在基础模型时代重新思考半监督医学图像分割|文献速递-深度学习人工智能医疗图像
  • 笔记：现代操作系统：原理与实现（2）