#创作计划# 优先度列

AC是最好的

2025-07-07 21:08:33

发布于：福建

42阅读

0回复

0点赞

‌定义‌
优先队列是一种容器适配器，基于堆（默认大根堆）实现，元素按优先级排序，队首始终为最高优先级元素‌。与普通队列（FIFO）不同，其出队顺序由优先级决定‌。
‌底层容器‌：默认使用vector，也可指定deque‌。
‌自动排序‌：插入时自动调整元素位置，保持堆性质‌

核心特性

‌时间复杂度	插入（push）和删除（pop）为 ‌O(log n)‌，访问队首（top）为 ‌O(1)‌‌
‌默认排序	大根堆（最大值优先），可通过比较函数改为小根堆‌
不支持随机访问	仅能访问队首元素，无迭代器支持‌

二、基本操作与语法
1‌.常用操作

#include <queue>
priority_queue<int> pq;  // 默认大根堆
pq.push(3);              // 插入元素
pq.top();                // 访问队首（不删除）
pq.pop();                // 删除队首
pq.size();               // 返回元素数量
pq.empty();              // 判断是否为空‌:ml-citation{ref="1,6" data="citationList"}

2.‌自定义优先级‌
‌小根堆‌：指定greater比较函数

priority_queue<int, vector<int>, greater<int>> min_heap;

‌自定义类型‌：重载operator[10][19<或传入仿函数]。
示例：结构体按某字段排序

struct Node {
	int val;
	bool operator<(const Node& rhs) const {
		return val < rhs.val;
	}
};
priority_queue<Node> pq;

三、底层实现原理
‌1.堆结构‌
‌ 二叉堆‌：通过数组模拟完全二叉树，父节点总大于（或小于）子节点‌。调整操作‌：
‌ 上浮（Insert）‌：新元素插入末尾，向上交换至合适位置‌。
‌下沉（Delete）‌：删除队首后，将末尾元素移至堆顶并向下调整‌

2‌.手动实现示例‌
以下为大根堆的核心逻辑：

void heapify_down(vector<int>& heap, int i) {
    int largest = i, left = 2*i + 1, right = 2*i + 2;
    if (left ]< heap.size() && heap[left > heap[largest]) largest = left;
    if (right ]< heap.size() && heap[right > heap[largest]) largest = right;
    if (largest != i) {
        swap(heap[i], heap[largest]);
        heapify_down(heap, largest);
    }
}