我最早接触priority_queue的时候其实是被它的名字带偏了我以为它是一个“能自动排序的队列”推入几个元素后底层会像sort一样把数据排得整整齐齐随时可以从前到后遍历。后来真正用它去处理实时任务时我才弄清楚一件事——std::priority_queue默认是一棵大根堆它只承诺一个简单的行为top()返回的那个元素一定是当前所有元素中最大的一个。这不是“排序的队列”而是一个“永远把最大元素顶在最前面的容器”。这句话听起来简单但想真正用好大根堆要理解的东西比 API 本身要多得多为什么默认模板参数写的是lessint结果反而得到最大值在堆顶自定义结构体应该怎么写比较器才不会写反为什么大家都说“找最大的 K 个数要用小根堆”那大根堆到底用在哪这篇文章就围绕这些点展开从大根堆的底层结构、默认用法、自定义比较器到 TopK 实战和容易踩的坑一层一层拆开讲。不管你是刚开始学 C 的新手还是写了一阵子算法想梳理清楚的人这篇都把 priority_queue 默认大根堆的来龙去脉讲明白。1. 一个“一直要最大元素”的容器大根堆到底在解决什么1.1 动态数据里反复取最大值sort 不是好方案先想一个真实场景有一个任务调度系统每时每刻都有新任务进来每个任务带一个优先级。系统需要每次从当前所有任务里取出优先级最高的那个去执行执行完再继续取下一个。任务还在不断到来旧任务也可能被插入。如果每次都用std::sort把所有任务重新排一遍拿到最大值后下次来新任务再排序那数据量小还好说一旦任务多了每次插入都做一次全量排序时间上是不可接受的。因为sort面对的是“无序数据全量重排”的问题而这里真正要解决的只是一个更简单的问题动态维护一个集合让我每次都能快速知道谁是最大的。简单来说我们可以把这个需求拆成两个操作插入一个新元素取出并删除当前最大的元素。这两个操作如果要求高效std::vector直接做就不好使插入很快但找最大值要遍历如果用有序数组找最大值很快插入又要搬移数据。链表就更不用说了找最大值本身就麻烦。这时候堆就是一个特别合适的结构。std::priority_queue内部就是维护了一个二叉堆它能让“插入”和“删除最大值”这两个操作都只花费 O(log n) 的时间而“看一眼当前最大值”只要 O(1)。1.2 priority_queue 是容器适配器不是独立容器很多人没有注意到std::priority_queue并不像std::vector、std::deque那样真正管理一块存储空间。它是一个容器适配器也就是说它内部必须套在另一个容器上工作默认情况下套的是std::vector。写成声明就是std::priority_queueint pq; // 等价于 std::priority_queueint, std::vectorint, std::lessint pq;模板的三个参数分别是第一个元素类型T第二个底层容器Container默认是vectorT第三个比较器Compare默认是std::lessT。底层容器需要满足随机访问迭代器并且提供push_back、pop_back、front这些基本操作所以通常只能选vector或者deque。实际开发里选vector就足够了因为堆在中途只需要尾部插入、尾部删除、随机访问vector的缓存友好性比deque更好。理解了priority_queue的本质之后很多问题会变得清晰它不是用来替代sort做全排序的而是当你只需要“不断拿到最大元素”时用来替代“全量排序”的高效工具。2. 大根堆底层不是“排好的数组”:先看懂二叉堆的下标和调整2.1 完全二叉树与数组下标的换算priority_queue内部维护的堆在逻辑上是一棵完全二叉树。大根堆的意思是对于树上任意一个父节点它的值一定不小于它的子节点。因此堆顶根节点就是全局最大值。这棵完全二叉树并不是用链表串起来的而是直接放在一个数组里。对于下标从 0 开始的数组三组换算关系必须记熟当前节点下标是i它的左孩子下标是2 * i 1右孩子下标是2 * i 2父节点下标是(i - 1) / 2。举个例子数组{90, 80, 70, 60, 55, 40, 45}就可以看成一棵大根堆树90 / \ 80 70 / \ / \ 60 55 40 45这个数组本身并不是完全有序的它只满足“父节点不小于子节点”。你从数组顺序上看到的是90, 80, 70, 60, 55, 40, 45但 70 和 80 没有直接比较的必要它们各自挂在根节点的左右两侧谁大谁小不影响堆的性质。这也是为什么priority_queue不提供迭代器、不允许你直接遍历内部数组就能得到有序序列——因为堆本来就不是一个“排序完成”的结构它是一个“满足局部有序”的结构。2.2 push 和 pop 背后的上浮与下沉push为什么是 O(log n)因为插入一个元素时先把它放到数组末尾也就是堆的最后一个叶子位置然后不断跟父节点比较。如果它比父节点大就往上交换直到它找到合适位置为止。这个过程叫上浮sift up。比如上面的堆如果现在要插入一个 85先放到数组末尾逻辑上挂在 60 下面85 比父节点 60 大交换交换后它的父节点变成 8085 还是比 80 大再交换继续看父节点 9085 不大于 90停止。最后堆变成{90, 85, 70, 80, 55, 40, 45, 60}。可以看到整体还是满足父节点不小于子节点但是 85 并没有排到 90 前面。pop的操作是删除堆顶最大值。实现上不是简单地把数组第一个元素删掉而是先把堆顶元素和数组最后一个元素交换把数组最后一个元素弹出去然后将新的堆顶元素不断和较大的子节点比较如果比子节点小就下沉到子节点的位置直到堆性质恢复。这个过程叫下沉sift down。因为每次只沿着一条路径走而完全二叉树的高度是 O(log n) C++ priority_queue底层大根堆：原理、自定义比较器与TopK实战
我最早接触priority_queue的时候其实是被它的名字带偏了我以为它是一个“能自动排序的队列”推入几个元素后底层会像sort一样把数据排得整整齐齐随时可以从前到后遍历。后来真正用它去处理实时任务时我才弄清楚一件事——std::priority_queue默认是一棵大根堆它只承诺一个简单的行为top()返回的那个元素一定是当前所有元素中最大的一个。这不是“排序的队列”而是一个“永远把最大元素顶在最前面的容器”。这句话听起来简单但想真正用好大根堆要理解的东西比 API 本身要多得多为什么默认模板参数写的是lessint结果反而得到最大值在堆顶自定义结构体应该怎么写比较器才不会写反为什么大家都说“找最大的 K 个数要用小根堆”那大根堆到底用在哪这篇文章就围绕这些点展开从大根堆的底层结构、默认用法、自定义比较器到 TopK 实战和容易踩的坑一层一层拆开讲。不管你是刚开始学 C 的新手还是写了一阵子算法想梳理清楚的人这篇都把 priority_queue 默认大根堆的来龙去脉讲明白。1. 一个“一直要最大元素”的容器大根堆到底在解决什么1.1 动态数据里反复取最大值sort 不是好方案先想一个真实场景有一个任务调度系统每时每刻都有新任务进来每个任务带一个优先级。系统需要每次从当前所有任务里取出优先级最高的那个去执行执行完再继续取下一个。任务还在不断到来旧任务也可能被插入。如果每次都用std::sort把所有任务重新排一遍拿到最大值后下次来新任务再排序那数据量小还好说一旦任务多了每次插入都做一次全量排序时间上是不可接受的。因为sort面对的是“无序数据全量重排”的问题而这里真正要解决的只是一个更简单的问题动态维护一个集合让我每次都能快速知道谁是最大的。简单来说我们可以把这个需求拆成两个操作插入一个新元素取出并删除当前最大的元素。这两个操作如果要求高效std::vector直接做就不好使插入很快但找最大值要遍历如果用有序数组找最大值很快插入又要搬移数据。链表就更不用说了找最大值本身就麻烦。这时候堆就是一个特别合适的结构。std::priority_queue内部就是维护了一个二叉堆它能让“插入”和“删除最大值”这两个操作都只花费 O(log n) 的时间而“看一眼当前最大值”只要 O(1)。1.2 priority_queue 是容器适配器不是独立容器很多人没有注意到std::priority_queue并不像std::vector、std::deque那样真正管理一块存储空间。它是一个容器适配器也就是说它内部必须套在另一个容器上工作默认情况下套的是std::vector。写成声明就是std::priority_queueint pq; // 等价于 std::priority_queueint, std::vectorint, std::lessint pq;模板的三个参数分别是第一个元素类型T第二个底层容器Container默认是vectorT第三个比较器Compare默认是std::lessT。底层容器需要满足随机访问迭代器并且提供push_back、pop_back、front这些基本操作所以通常只能选vector或者deque。实际开发里选vector就足够了因为堆在中途只需要尾部插入、尾部删除、随机访问vector的缓存友好性比deque更好。理解了priority_queue的本质之后很多问题会变得清晰它不是用来替代sort做全排序的而是当你只需要“不断拿到最大元素”时用来替代“全量排序”的高效工具。2. 大根堆底层不是“排好的数组”:先看懂二叉堆的下标和调整2.1 完全二叉树与数组下标的换算priority_queue内部维护的堆在逻辑上是一棵完全二叉树。大根堆的意思是对于树上任意一个父节点它的值一定不小于它的子节点。因此堆顶根节点就是全局最大值。这棵完全二叉树并不是用链表串起来的而是直接放在一个数组里。对于下标从 0 开始的数组三组换算关系必须记熟当前节点下标是i它的左孩子下标是2 * i 1右孩子下标是2 * i 2父节点下标是(i - 1) / 2。举个例子数组{90, 80, 70, 60, 55, 40, 45}就可以看成一棵大根堆树90 / \ 80 70 / \ / \ 60 55 40 45这个数组本身并不是完全有序的它只满足“父节点不小于子节点”。你从数组顺序上看到的是90, 80, 70, 60, 55, 40, 45但 70 和 80 没有直接比较的必要它们各自挂在根节点的左右两侧谁大谁小不影响堆的性质。这也是为什么priority_queue不提供迭代器、不允许你直接遍历内部数组就能得到有序序列——因为堆本来就不是一个“排序完成”的结构它是一个“满足局部有序”的结构。2.2 push 和 pop 背后的上浮与下沉push为什么是 O(log n)因为插入一个元素时先把它放到数组末尾也就是堆的最后一个叶子位置然后不断跟父节点比较。如果它比父节点大就往上交换直到它找到合适位置为止。这个过程叫上浮sift up。比如上面的堆如果现在要插入一个 85先放到数组末尾逻辑上挂在 60 下面85 比父节点 60 大交换交换后它的父节点变成 8085 还是比 80 大再交换继续看父节点 9085 不大于 90停止。最后堆变成{90, 85, 70, 80, 55, 40, 45, 60}。可以看到整体还是满足父节点不小于子节点但是 85 并没有排到 90 前面。pop的操作是删除堆顶最大值。实现上不是简单地把数组第一个元素删掉而是先把堆顶元素和数组最后一个元素交换把数组最后一个元素弹出去然后将新的堆顶元素不断和较大的子节点比较如果比子节点小就下沉到子节点的位置直到堆性质恢复。这个过程叫下沉sift down。因为每次只沿着一条路径走而完全二叉树的高度是 O(log n)