《priority_queue：藏在堆里的 “优先级管家”》

LOTSO

发布于 2025-10-29 15:27:29

7200

代码可运行

文章被收录于专栏：C++C++

运行总次数：0

代码可运行

�

🎬 博主简介：

前言：

在 STL 中，priority_queue（优先队列）是处理优先级任务的实用工具 —— 以堆结构为核心，封装复杂排序逻辑，能高效获取优先级最高的元素，广泛用于 Top K、任务调度等场景。要用好它，需理清关键逻辑：底层为何选 vector？如何切换大堆与小堆？本文将拆解其特性、接口与原理，帮你从 “会用” 到 “懂原理”。

一. priority_queue 核心逻辑与底层揭秘

1.1 本质与优先级规则

priority_queue 是 STL 中的容器适配器，本质基于 “堆” 数据结构实现，核心特性是 “始终让堆顶元素为当前容器中优先级最高的元素”，默认按 “大堆” 规则排序（即堆顶为最大值）。

容器适配器属性：不直接存储数据，而是封装底层容器（如 vector、deque），并通过堆算法（make_heap、push_heap、pop_heap）来维护堆结构。
优先级规则：默认是大堆（堆顶为最大元素），可通过指定比较规则改为小堆；优先级由比较函数决定，支持内置类型和自定义类型。

参考文档：priority_queue - C++ Reference

1.2 底层容器的适配要求

底层容器需支持 “随机访问迭代器” 和以下操作，STL 中默认使用 vector（空间连续，堆算法效率更高），也可指定 deque：

empty()：检测是否为空
size()：返回元素个数
front()：访问堆顶元素（即容器首元素）
push_back()：在容器尾部插入元素（用于后续堆调整）
pop_back()：删除容器尾部元素（配合堆调整移除堆顶）

1.3 常用接口与场景示例

接口声明	功能说明
priority_queue()	构造一个空的优先队列，初始化后无任何元素，需通过 push(x) 插入数据。
priority_queue(first, last)	利用迭代器区间 [first, last] 中的所有元素初始化优先队列，初始化后会自动调整为堆结构。
empty()	检测优先队列是否为空，若队列中无元素则返回 true，存在元素则返回 false，常用于判断是否可执行 top() 或 pop() 操作。
size()	返回优先队列中有效元素的个数，可用于了解队列数据量，或配合循环控制 pop() 操作次数（如 Top K 问题中弹出前 K-1 个元素）。
top()	返回堆顶元素的引用，大堆场景下返回队列中的最大值，小堆场景下返回最小值；需注意，调用前需用 empty() 确认队列非空，否则会触发未定义行为。
push(x)	将元素 x 插入优先队列的尾部，插入后会自动调用堆算法（push_heap）调整堆结构，确保队列仍满足大堆或小堆的排序规则。
pop()	删除优先队列的堆顶元素，删除前会先通过堆算法（pop_heap）将堆顶元素交换到队列尾部，再执行删除；操作后需确保队列非空，且删除后仍保持堆结构。

实际案例：

// 仿函数/函数对象   对象可以像函数一样使用
template <class T> 
struct Less
{
	bool operator() (const T& x, const T& y) const { return x < y; }
};

#include<queue>
int main()
{
	//priority_queue<int> pq;//默认是大的优先级高(大堆)
	priority_queue<int,vector<int>,greater<int>> pq;//调整成默认是小的优先级高(小堆)
	pq.push(3);
	pq.push(1);
	pq.push(2);
	pq.push(4);
	pq.push(6);

	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}

	return 0;
}

二. priority_queue 底层实现解析

2.1 关键接口的代码实现(注意看注释)

#pragma once
#include <vector>
using namespace std;

namespace Lotso {
    // 比较器：用于大堆（父节点优先级高于子节点时，返回true触发交换）
    template <class T>
    struct Less {
        bool operator()(const T& x, const T& y) const {
            return x < y;  // 当x < y时，说明y优先级更高，返回true
        }
    };

    // 比较器：用于小堆（子节点优先级高于父节点时，返回true触发交换）
    template <class T>
    struct Greater {
        bool operator()(const T& x, const T& y) const {
            return x > y;  // 当x > y时，说明y优先级更高，返回true
        }
    };

    // 优先队列类模板
    // T：存储的元素类型；Container：底层容器（默认vector，需支持随机访问和尾部操作）
    // Compare：比较器（默认Less，即大顶堆）
    template <class T, class Container = vector<T>, class Compare = Less<T>>
    class priority_queue {
    private:
        Container _con;  // 底层容器，实际存储元素的空间

        // 向上调整：插入新元素后，将其移动到正确位置以维持堆结构
        // 参数child：新元素在容器中的索引（初始为尾部）
        void adjust_up(int child) {
            Compare com;  // 实例化比较器，用于判断优先级
            int parent = (child - 1) / 2;  // 计算父节点索引（通过子节点索引推导）
            
            // 当子节点未到达根节点（索引0）时，持续调整
            while (child > 0) {
                // 若父节点优先级低于子节点，交换两者
                if (com(_con[parent], _con[child])) {
                    swap(_con[child], _con[parent]);
                    child = parent;  // 更新子节点为原父节点位置
                    parent = (child - 1) / 2;  // 重新计算父节点索引
                } else {
                    break;  // 已满足堆结构，停止调整
                }
            }
        }

        // 向下调整：删除堆顶元素后，将新堆顶移动到正确位置以维持堆结构
        // 参数parent：需要调整的节点索引（初始为根节点0）
        void adjust_down(int parent) {
            Compare com;  // 实例化比较器
            int child = 2 * parent + 1;  // 计算左孩子索引（默认先比较左孩子）
            
            // 当子节点未超出容器范围时，持续调整
            while (child < _con.size()) {
                // 若右孩子存在且优先级高于左孩子，选择右孩子进行比较
                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 = 2 * parent + 1;  // 重新计算左孩子索引
                } else {
                    break;  // 已满足堆结构，停止调整
                }
            }
        }

    public:
        // 迭代器区间构造：用[first, last)范围内的元素初始化队列，并构建堆
        template <class InPutIterator>
        priority_queue(InPutIterator first, InPutIterator last) : _con(first, last) {
            // 从最后一个非叶子节点开始向下调整，完成堆的构建
            // 最后一个非叶子节点索引 = (元素总数 - 2) / 2（整数除法）
            for (int i = (_con.size() - 2) / 2; i >= 0; i--) {
                adjust_down(i);
            }
        }

        // 默认构造函数：创建空队列
        priority_queue() = default;

        // 插入元素：将元素添加到容器尾部，再通过向上调整维持堆结构
        void push(const T& x) {
            _con.push_back(x);
            adjust_up(_con.size() - 1);  // 新元素索引为容器当前最后位置
        }

        // 删除堆顶元素：
        // 1. 交换堆顶（首元素）和尾部元素
        // 2. 删除尾部元素（原堆顶）
        // 3. 对新堆顶（原尾部元素）执行向下调整
        void pop() {
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            if (!empty()) {  // 若队列非空，需调整堆结构
                adjust_down(0);
            }
        }

        // 获取堆顶元素（非const版本，可用于修改元素）
        const T& top() {
            return _con[0];  // 堆顶元素即容器首元素
        }

        // 获取堆顶元素（const版本，用于const对象，不可修改元素）
        const T& top() const {
            return _con[0];
        }

        // 判断队列是否为空（非const版本）
        bool empty() {
            return _con.empty();
        }

        // 判断队列是否为空（const版本）
        bool empty() const {
            return _con.empty();
        }

        // 获取队列中元素个数（非const版本）
        size_t size() {
            return _con.size();
        }

        // 获取队列中元素个数（const版本）
        size_t size() const {
            return _con.size();
        }
    };
}

2.2 测试用例与验证

测试用例一：测试自定义优先级队列

#include "priority_queue.h"

void test_pq1()
{
	//Lotso::priority_queue<int> pq;
	int a[] = { 30,4,2,66,3 };
	//Lotso::priority_queue<int> pq(a, a + 5);
	Lotso::priority_queue<int, vector<int>, Lotso::Greater<int>> pq(a, a + 5);
	pq.push(3);
	pq.push(1);
	pq.push(5);
	pq.push(7);
	pq.push(2);

	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

int main()
{
	test_pq1();
	return 0;
}

测试用例二：测试仿函数的使用 1.存储指针的优先级队列

class Date
{
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{
	}
	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend ostream& operator<<(ostream& _cout, const Date& d)
	{
		_cout << d._year << "-" << d._month << "-" << d._day;
		return _cout;
	}
private:
	int _year;
	int _month;
	int _day;
};

struct PDateless
{
	bool operator()(const Date* p1, const Date* p2)
	{
		return *p1 < *p2;
	}
};

void test_pq2()
{
	//如果我们使用的是Date*而不是Date
	//Lotso::priority_queue<Date*> q1;//这样写打印出来既不是大堆也不是小堆
	//是因为我们如果这样写就相当于在比较指针，
	//所以我们这里可以先定义一个仿函数来实现比较(后面在模板的进阶那里还会讲解别的方法)

	Lotso::priority_queue < Date*, vector<Date*>, PDateless> q1;//这样就可以了
	q1.push(new Date(2025, 10, 18));
	q1.push(new Date(2025, 10, 19));
	q1.push(new Date(2025, 10, 20));

	while (!q1.empty())
	{
		cout << *q1.top() << endl;
		q1.pop();
	}
	cout << endl;
}

int main()
{
	//test_pq1();
	test_pq2();
	return 0;
}

2.仿函数在使用上的一些小区别(sort怎么改降序)

//那么仿函数=也有一些对应的其它使用场景
void test1()
{
	vector<int> v1 = { 7,6,8,9,5,7,10 };
	//默认其实里面也有个仿函数less <:升序
	//替换成greater<>() >:降序
	sort(v1.begin(), v1.end());
	for (auto& x : v1)
	{
		cout << x << " ";
	}
	cout << endl;
	//大家有没有发现这里的greater使用的时候比优先队列多个()，我们看看下面的图片。
	sort(v1.begin(), v1.end(), greater<int>());
	for (auto& x : v1)
	{
		cout << x << " ";
	}
	cout << endl;
}

int main()
{
	test1();
	return 0;
}

测试用例三：仿函数的应用拓展

struct Option
{
	bool operator()(int x)
	{
		return x % 2 == 0;
	}
};
void test2()
{
	vector<int> v2 = { 1,2,3,4,5,6,7,8 };
	//查找第一个偶数
	auto it = find_if(v2.begin(), v2.end(), Option());
	cout << *it << endl;

	list<int> l1 = { 1,2,5,6,7,9,10 };

	//删除偶数
	l1.remove_if(Option());

	for (auto& x : l1)
	{
		cout << x << " ";
	}
	cout << endl;
}

int main()
{
	//test1();
	test2();
	return 0;
}

三. OJ实战练习：数组中第k个最大的元素

题目链接：

215. 数组中的第K个最大元素 - 力扣（LeetCode）

题目描述：

题目示例：

C++算法代码：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 将数组中的元素先放入优先级队列中
        priority_queue<int> q1(nums.begin(),nums.end());
        for(int i=0;i<k-1;i++)
            q1.pop();
        
        return q1.top();
    }
};

结尾：

🍓 我是草莓熊 Lotso！若这篇技术干货帮你打通了学习中的卡点：
👀 【关注】跟我一起深耕技术领域，从基础到进阶，见证每一次成长
❤️ 【点赞】让优质内容被更多人看见，让知识传递更有力量
⭐ 【收藏】把核心知识点、实战技巧存好，需要时直接查、随时用
💬 【评论】分享你的经验或疑问（比如曾踩过的技术坑？），一起交流避坑
🗳️ 【投票】用你的选择助力社区内容方向，告诉大家哪个技术点最该重点拆解
技术之路难免有困惑，但同行的人会让前进更有方向～愿我们都能在自己专注的领域里，一步步靠近心中的技术目标！

结语：作为 STL 中基于堆结构实现的容器适配器，priority_queue 用简洁的接口封装了复杂的堆调整逻辑 —— 无论是默认的大堆排序，还是自定义类型的优先级适配，都能轻松应对 “按优先级取元素” 的需求。从日常的任务调度到 OJ 中的 Top K 问题，它既能简化代码编写，又能保证高效的时间复杂度，堪称处理优先级场景的 “实用工具”。掌握它的底层逻辑与使用技巧，能让我们在面对类似需求时，快速找到简洁且高效的解决方案。