C++二叉堆（priority_queue）

hlb20130715

204人浏览 · 2025-11-11 21:52:21

hlb20130715 · 2025-11-11 21:52:21 发布

二叉堆是完全二叉树的特殊形式，分两种：

- 大根堆：父节点值≥左右子节点值（堆顶为最大值）

- 小根堆：父节点值≤左右子节点值（堆顶为最小值）

//模板参数：元素类型，底层容器（默认vector），比较器（默认less<T>大根堆）
priority_queue<T,Container,Compare>pq;

//示例
priority_queue<int>pq1;//大根堆（默认）：less<int>，底层vector<int>
priority_queue<int,vector<int>,greater<int>>pq2;//小根堆

操作	功能	时间复杂度	内部逻辑
push(x)	插入元素 x	O(logn)	放数组尾部，通过 “上浮” 调整堆
pop()	删除堆顶元素	O(logn)	交换堆顶与最后元素，删尾部，新堆顶 “下沉” 调整
top()	获取堆顶元素（最值）	O(1)	返回数组首元素（根节点）
empty()	判断是否为空	O(1)	检查底层容器是否为空
size()	获取元素个数	O(1)	返回底层容器大小

//例：用小根堆求数组前k大
vector<int>topK(vector<int>&nums,int k){
    priority_queue<int,vector<int>,greater<int>>pq;//小根堆（容量保持k）
    for(int x:nums){
        pq.push(x);
        if(pq.size()>k)pq.pop();//超过k则删除最小值（堆顶）
    }
    //最终堆中元素为前k大
    vector<int>res;
    while(!pq.empty()){
        res.push_back(pq.top());
        pq.pop();
    }
    return res;
}

嘤嘤嘤，不想手写……