搜索引擎优化的完整过程_tpshop开源商城_百度seo学院_社区推广方法有哪些

一、基本概念与特性

priority_queue 是 C++ STL 中的容器适配器，基于堆数据结构实现，支持按优先级动态管理元素。其核心特性包括：

• 优先级排序：默认大顶堆（最大元素在堆顶），可通过自定义比较器改为小顶堆。
• 操作限制：仅允许访问堆顶元素（top()），不支持遍历和随机访问。
• 底层容器：默认使用 vector，也可用 deque，需支持 push_back()、pop_back() 和随机访问迭代器 。

二、基本用法

1. 初始化与声明

#include <queue>
#include <functional> // 用于 greater/less// 默认大顶堆（最大元素在堆顶）
priority_queue<int> max_heap; // 小顶堆（需显式指定容器和比较器）
priority_queue<int, vector<int>, greater<int>> min_heap;// 自定义比较器（需返回优先级判断）
struct Compare {bool operator()(int a, int b) { return a > b; } // 小顶堆
};
priority_queue<int, vector<int>, Compare> custom_heap;

2. 常用操作

操作	函数/语法	说明
插入元素	push(val)	插入元素并调整堆结构
删除堆顶元素	pop()	移除堆顶元素并调整堆
访问堆顶元素	top()	返回当前优先级最高的元素
判空	empty()	检查队列是否为空
获取元素数量	size()	返回队列中元素的数量

3. 自定义数据类型示例

class Person {
public:string name;int age;// 重载运算符或定义比较器bool operator<(const Person& p) const { return age < p.age; } // 大顶堆
};// 使用自定义比较器
struct CompareAge {bool operator()(Person& a, Person& b) { return a.age > b.age; } // 小顶堆
};
priority_queue<Person, vector<Person>, CompareAge> age_queue;

三、底层实现原理

1. 堆结构

• 完全二叉树：堆通过数组（如 vector）模拟完全二叉树，满足：
  • 父节点下标 i，左子节点 2i+1，右子节点 2i+2 。
     
  • 大顶堆：父节点值 ≥ 子节点；小顶堆：父节点值 ≤ 子节点。
     
• 堆调整算法：
  • 向上调整（sift up）：插入元素时，从叶节点向上比较并交换，直到满足堆性质。
     
  • 向下调整（sift down）：删除堆顶时，将末尾元素移到堆顶，再向下比较交换。
     

2. 核心操作实现

• 插入（push）：
  1. 将元素添加到数组末尾。
  2. 向上调整至合适位置（时间复杂度：O(log n)）。
      
• 删除堆顶（pop）：
  1. 交换堆顶与末尾元素。
  2. 移除末尾元素。
  3. 从堆顶向下调整（时间复杂度：O(log n)）。
      

3. 建堆时间复杂度

• 批量建堆：从最后一个非叶节点开始向下调整，总时间复杂度为 O(n)（非 O(n log n)） 。

低层节点占多数：约 n/2 的节点是叶子节点，无需调整；次底层节点（数量为 n/4）仅需调整1次，依此类推

四、复杂度分析

操作	时间复杂度	空间复杂度
插入元素 (push)	O(log n)	O(1)
删除堆顶 (pop)	O(log n)	O(1)
访问堆顶 (top)	O(1)	O(1)
判空 (empty)	O(1)	O(1)

五、应用场景

1. 任务调度：优先处理高优先级任务。
2. 算法优化：如 Dijkstra 算法中选择最短路径。
    
3. Top K 问题：快速筛选最大/最小的 K 个元素。

六、注意事项

1. 比较器方向：Compare 返回 true 表示第一个参数优先级更低（更晚出队） 。
    
2. 容器要求：底层容器需支持 front()、push_back() 和 pop_back()  。
    
3. 无迭代器：无法遍历元素，仅能通过 top() 访问堆顶