堆
2025-06-22 15:32:07
发布于：上海
9阅读
0回复
0点赞
堆是一种数组对象，它可以被视为一棵完全二叉树。
跟完全二叉树的区别
它只有大根堆（父亲节点>=儿子节点）和小根堆（儿子节点>=父亲节点）<--堆
和排序二叉树的区别是：排序二叉树是 左孩子<=父亲节点<=右孩子 <--非堆，单独成一种
不过，下面的内容和排序二叉树完全没有关系
独属于完全二叉树的存图方式
首先，逐个编号，接下来，挨个存图就行了~（太高贵了）
那怎么取节点呢？设父亲的编号为i，那么左孩子=2i，右孩子=2i+1，父亲节点就是左孩子 or 右孩子 /2
堆的两种操作
1、put：加入一个元素，原理就是每次和父亲节点比较，若自己大于父亲节点，他俩就交换，知道到达适合的位置
代码模板：
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;
}
}
2、get：取出并删除一个元素，原理和put差不多，就是方向反一反。
代码模板：
int get(int d){
int son,pa,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;
}
优先队列和堆的关系
priority_queue<int> pq;
int x=pq.top();
top()=get()+put();
pop()=get();
size,empty()=head_size;
有帮助，赞一个