C++中如何使用priority_queue实现堆排序？优先队列堆排序方法详解

在C++里，priority_queue是标准库提供的容器适配器，它默认以vector为底层容器，并用大顶堆的方式管理元素。利用这一特性，我们可以非常简洁地实现堆排序，而不必手动编写上浮和下沉操作。

一、使用默认大顶堆实现降序排序

默认情况下，priority_queue的队首元素始终是最大值。我们把所有元素放入队列后，依次弹出，就能得到从大到小的序列。

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    vector<int> data = {5, 2, 8, 1, 9, 3};
    // 默认大顶堆，底层容器为vector，比较函数为less<int>
    priority_queue<int> pq;
    for (int x : data) {
        pq.push(x);
    }
    // 依次弹出得到降序结果
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    return 0;
}

二、使用小顶堆实现升序排序

如果希望得到升序结果，可以在声明时指定比较器为greater<int>，这样底层会变成小顶堆，队首始终是最小值。

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

int main() {
    vector<int> data = {5, 2, 8, 1, 9, 3};
    // 小顶堆：第三个模板参数为greater<int>
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : data) {
        pq.push(x);
    }
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    return 0;
}

三、对自定义结构体的排序

当待排序元素是自定义类型时，需要重载operator<或者传入自定义比较函数对象，以告诉优先队列如何确定优先级。

#include <iostream>
#include <queue>
#include <string>

using namespace std;

struct Task {
    int level;
    string name;
    // level越大优先级越高
    bool operator<(const Task& other) const {
        return level < other.level;
    }
};

int main() {
    priority_queue<Task> pq;
    pq.push({2, "low"});
    pq.push({5, "high"});
    pq.push({3, "mid"});
    while (!pq.empty()) {
        Task t = pq.top();
        cout << t.name << " ";
        pq.pop();
    }
    return 0;
}

四、时间复杂度说明

将n个元素插入priority_queue，每次插入为O(log n)，总共O(n log n)；弹出n次同样是O(n log n)。因此用priority_queue实现的堆排序整体时间复杂度为O(n log n)，空间上额外占用一个队列容器。

五、小结

使用C++的priority_queue实现堆排序非常直观：把数据推入队列，再根据大顶堆或小顶堆特性弹出即可。对于基础类型，通过greater切换升序；对于自定义类型，重写比较逻辑就能灵活控制排序规则。

priority_queue堆排序C++修改时间：2026-07-28 07:45:18