关于堆的put和get的操作（自留）
2026-01-03 11:47:48
发布于：四川
4阅读
0回复
0点赞
put：用于往堆中插入元素（建立堆）
/*
堆：
操作 1.put
使用put实现小根堆：
准备： 建立一个数组heap[100010],初始长度为len=0；
step1：在堆尾加入一个元素，并把这个节点设置为当前结点
step2：比较当前结点和它父节点的大小：
如果小于，交换，继续步骤2
如果·大于，结束
重复n此操作，可获得一个结点为n的小根堆
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
int heap[maxn];
int heap_size;
void put(int d){
int son,pa;//定义儿子和父亲
heap[++heap_size]=d;
son=heap_size;
while(son>1){
pa = son>>1;//找到父节点
if(heap[son]<=heap[pa]) break;//判断
swap(heap[son],heap[pa]);//否则就调换位置
son = pa;
}
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;++i){
int x;cin>>x;put(x);
}
for(int i=1;i<=n;++i){
cout<<heap[i];
}
return 0;
}
get：用于删除堆中元素
/*
堆操作：get
使用get删除元素；
step1 取出堆的根节点的值
step2 把堆的最后一个结点len放在根的位置上，把根覆盖掉。把堆的长度减一。
step3 把根节点置为当前父节点parent
step4 如果parent无儿子结束 否则把parent的两个或一个儿子中的最小值设置为当前子节点son
step5 比较parent和son的值 若parent小于son结束，否则交换二者的值，让pa指向son，继续执行step4
*/
int get(){
int pa,son,res;
res=heap[1];//存储堆顶元素
heap[1]=heap[heap_size--];//用最后一个元素覆盖堆顶元素
pa = 1;
//向下做调整（重新构造）
while(pa*2<=heap_size){
son=pa*2;//左儿子
if(son<heap_size&&heap[son+1]<heap[son]) son++;//比较左儿子和右儿子（找到存在儿子中最大的一个）
if(heap[pa]<=heap[son]) break;//比较父节点和子节点大小（是否需要交换）
swap(heap[pa],heap[son]);
pa=son;
}
return res;
}
全部评论 2
补一下get的完整代码
/* 堆操作：get 使用get删除元素； step1 取出堆的根节点的值 step2 把堆的最后一个结点len放在根的位置上，把根覆盖掉。把堆的长度减一。 step3 把根节点置为当前父节点parent step4 如果parent无儿子结束 否则把parent的两个或一个儿子中的最小值设置为当前子节点son step5 比较parent和son的值 若parent小于son结束，否则交换二者的值，让pa指向son，继续执行step4 */ #include<bits/stdc++.h> using namespace std; int get(){ int pa,son,res; res=heap[1];//存储堆顶元素 heap[1]=heap[heap_size--];//用最后一个元素覆盖堆顶元素 pa = 1; //向下做调整（重新构造） while(pa*2<=heap_size){ son=pa*2;//左儿子 if(son<heap_size&&heap[son+1]<heap[son]) son++;//比较左儿子和右儿子（找到存在儿子中最大的一个） if(heap[pa]<=heap[son]) break;//比较父节点和子节点大小（是否需要交换） swap(heap[pa],heap[son]); pa=son; } return res; } int main(){ int n; cin>>n; for(int i=1;i<=n;++i){ int x; cin>>x; put(x); } while(heap_size) cout<<get()<<" "; return 0; }5天前 来自 四川
0
有帮助，赞一个