堆学习笔记

༺དༀ༒∞░∞༒ༀཌ༻（不加团）

2026-01-18 08:14:41

发布于：浙江

369阅读

0回复

0点赞

叠甲：

本文为学习笔记，非创作计划。所以格式上的问题，大佬喷轻点。

堆及堆的性质

堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。

每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆．STL 中的 priority_queue 其实就是一个大根堆。

（小根）堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。

-- OI wiki

堆使用数组进行储存。对于第 $i$ 个节点，其父节点下标为 $\frac{i}{2}$ ，左右孩子节点下标分别为 $2 \times i$ 与 $2\times i+1$ 。

（小根）堆元素的插入与取出

在堆尾加入该元素，并把这个节点设为当前节点。
比较当前节点与父节点的大小：

2.1 如果当前节点小于父节点，交换他们的值，并把父节点设为当前节点，重复步骤 2。

2.2 若当前节点大于父节点，或该节点已经为根节点，停止。

小根堆插入代码实现：

void push(int x){
    int son,pa;//当前节点与父节点
    heap[++siz]=x;//将当前要插入的数放到堆尾
    son=siz;
    while(son>1){
        pa=son/2;
        if(heap[son]<=heap[pa])break;
        swap(heap[pa],heap[son]); 
        son=pa;
    }
}

取出堆的根结点的值
把堆的最后一个结点（len）放到根的位置上，把根覆盖掉。把堆的长度减一。
把根结点置为当前父结点。
如果当前父节点无儿子（ $parent >len/2$ ），则结束；否则，把当前父节点的两（或一）个儿子中值最小的那个设置为当前的子结点。
比较当前父节点与当前子节点的值，如果当前父节点的值小于或等于当前子节点的值，则结束；否则，交换这两个结点的值，把当前父节点指向当前子节点，继续执行步骤 4。

小根堆取出当前节点并删除当前节点代码实现（这里分为 top 和 pop ）

int top(){
    return heap[1];
}
void pop(){
    int pa,son;//同上，这里不多赘述
    heap[1]=heap[siz--];
    pa=1;
    while(pa*2<=siz){
        son=2*pa;
        if(son<siz and heap[son]<heap[son+1])son++;
        if(heap[son]<=heap[pa])break;
        swap(heap[pa],heap[son]);
        pa=son;
    }
}

手写堆模版：

小根堆：

struct Heap{
    int heap[100005],siz=0;
    void push(int x){//插入
        int son,pa;
        heap[++siz]=x;
        son=siz;
        while(son>1){
            pa=son/2;
            if(heap[pa]<=heap[son])break;
            swap(heap[pa],heap[son]); 
            son=pa;
        }
    }int top(){//取出根节点
        return heap[1];
    }
    void pop(){//删除根节点
        int pa,son;
        heap[1]=heap[siz--];
        pa=1;
        while(pa*2<=siz){
            son=2*pa;
            if(son<siz and heap[son+1]<heap[son])son++;
            if(heap[pa]<=heap[son])break;
            swap(heap[pa],heap[son]);
            pa=son;
        }
    }int size(){//求当前堆的大小
        return siz;
    }bool empty(){//判空
        return siz; 
    }
};

大根堆：

struct Heap{
    int heap[100005],siz=0;
    void push(int x){
        int son,pa;
        heap[++siz]=x;
        son=siz;
        while(son>1){
            pa=son/2;
            if(heap[son]<=heap[pa])break;
            swap(heap[pa],heap[son]); 
            son=pa;
        }
    }int top(){
        return heap[1];
    }
    void pop(){
        int pa,son;
        heap[1]=heap[siz--];
        pa=1;
        while(pa*2<=siz){
            son=2*pa;
            if(son<siz and heap[son]<heap[son+1])son++;
            if(heap[son]<=heap[pa])break;
            swap(heap[pa],heap[son]);
            pa=son;
        }
    }int size(){
        return siz;
    }bool empty(){
        return siz; 
    }
};

真题演练：

题目

题目大意：

给你 $N$ 个数，要求输出他们从小到大排列的结果。

思路：

这里我们使用堆排序。
很简单，首先构建一个堆，将这 $N$ 个数放入堆。之后取出所有元素并输出即可。注意这里使用小根堆。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int read(){
    int x=0,f=1;
    int ch=getchar();
    while(ch<'0' or ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }while(ch>='0' and ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }return x*f;
}
void write(int x){
    if(x==0){
        putchar('0');
        return ;
    }if(x<0){
        putchar('-');
        x=-x;
    }if(x>9)write(x/10);
    putchar(x%10+'0');
}
struct Heap{
    int heap[100005],siz=0;
    void put(int x){
        int son,pa;
        heap[++siz]=x;
        son=siz;
        while(son>1){
            pa=son/2;
            if(heap[pa]<=heap[son])break;
            swap(heap[pa],heap[son]); 
            son=pa;
        }
    }int top(){
        return heap[1];
    }
    void pop(){
        int pa,son;
        heap[1]=heap[siz--];
        pa=1;
        while(pa*2<=siz){
            son=2*pa;
            if(son<siz and heap[son+1]<heap[son])son++;
            if(heap[pa]<=heap[son])break;
            swap(heap[pa],heap[son]);
            pa=son;
        }
    }int size(){
        return siz;
    }bool empty(){
        return siz; 
    }
};
signed main(){
    int a;
    cin >> a;
    Heap heap;
    for(int i=1;i<=a;i++){
        int x;
        x=read();
        heap.put(x);
    }for(int i=1;i<=a;i++){
        write(heap.top());
        putchar(' ');
        heap.pop();
    }
    return 0;
}

超市

题目大意：

超市里有 $N$ 件商品，每件商品都有利润 $p_i$ 和过期时间 $d_i$ ，每天只能卖一件商品，过期商品不能再卖。

求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。

其中 $N\leq 2\times 10^5$ 。

本题有两种做法，一种是采用贪心的策略，但是可能会爆。所以我们用堆。

先预处理所有商品，构建一个结构体并按照过期时间进行排序。

建立一个小根堆（这里采用 STL 容器的方式）。由于一天只能卖一个商品，所以堆的大小就是卖商品的天数。如果当前的商品过期天数与当前卖商品的天数相等，我们就看堆顶的那件商品（因为是小根堆，所以这件商品的收益肯定最小）的收益，如果比这件商品小，我们就替换掉。否则直接添加至堆中即可（因为已经排过序了）。

CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int p,d;
}sz[1000005];
bool cmp(node a,node b){
    return a.d<b.d;
}
signed main(){
    int n,ans=0;
    cin >> n;
    for(int i=1;i<=n;i++)cin >> sz[i].p >> sz[i].d;
    sort(sz+1,sz+n+1,cmp);
    priority_queue<int, vector<int>, greater<int>> heap;
    for(int i=1;i<=n;i++){
        if(sz[i].d==heap.size()){
            if(sz[i].p>heap.top()){ 
                heap.pop();
                heap.push(sz[i].p);
            }
        }else heap.push(sz[i].p); 
    }while(heap.size()){
        ans+=heap.top();
        heap.pop();
    }cout << ans;
}