堆学习笔记
2026-01-10 20:32:21
发布于：浙江
22阅读
0回复
0点赞
叠甲：
本文为学习笔记，非创作计划。所以格式上的问题，大佬喷轻点。
堆及堆的性质
堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。
每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆．STL 中的 priority_queue 其实就是一个大根堆。
（小根）堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。
-- OI wiki
堆使用数组进行储存。对于第 个节点，其父节点下标为 ，左右孩子节点下标分别为 与 。
（小根）堆元素的插入与取出
-
在堆尾加入该元素，并把这个节点设为当前节点。
-
比较当前节点与父节点的大小：
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）放到根的位置上，把根覆盖掉。把堆的长度减一。
-
把根结点置为当前父结点 。
-
如果当前父节点无儿子（），则结束；否则，把当前父节点的两（或一）个儿子中值最小的那个设置为当前的子结点。
-
比较当前父节点与当前子节点的值，如果当前父节点的值小于或等于当前子节点的值，则结束；否则，交换这两个结点的值，把当前父节点指向当前子节点，继续执行步骤 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;
}
};
真题演练：
题目：
题目大意：
给你 个数，要求输出他们从小到大排列的结果。
思路：
这里我们使用堆排序。
很简单，首先构建一个堆，将这 个数放入堆。之后取出所有元素并输出即可。注意这里使用小根堆。
代码：
#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;
}
THE END
后序还会更新o
有帮助，赞一个