堆 笔记及代码#AK-B##创作计划#
2025-06-21 16:51:04
发布于：上海
8阅读
0回复
0点赞
笔记：
· 堆是完全二叉树，分为大根堆和小根堆
· 大根堆的性质：父节点≥子节点
· 小根堆的性质：父节点≤子节点
代码：
小根堆put()操作代码实现：
void put(int d){
int son,pa;
//新增一个结点，值为d
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;
}
}
小根堆get()操作代码实现：
//返回堆顶的值，并删除堆顶
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]);//完毕调整
swap(heap[pa],heap[son]);//向下调整
pa=son;
}
return res;//返回堆顶的值
}
可替代以上代码的代码：
priority_queue<int>pq;//若为小根堆，此行应改为priority_queue<int,vector<int>,greater<int>>pq;
int x=pq.top();
top()=get()+put();
pop()=get();
size,empty()=head_size;
扩展：
· 排序二叉树的性质：左子节点 ≤ 父节点 ≤ 右子节点
感谢阅读，点个赞吧！
这里空空如也
有帮助，赞一个