数据结构与算法（3）——二叉堆
#include<iostream>
using namespace std;
const int HEAP_SIZE = 100;
void sink(int fa);
void swim(int son);
int heap[HEAP_SIZE+1];
int hs;
//以建立最小堆为例
/*****************************************************************/
//删除堆顶元素 ，利用上游函数调整
/*
删除最小值(deleteMin) 先用最后一个元素代替根
由于这一步会导致根的元素比儿子大，因此需要向下调整。向下调整的方法很简
单，就是把根和较小儿子做比较，如果根比较大，则交换它和儿子，算
法好比石沉大海，因此有的书把它称为sink过程
*/
int deleteMin(){
int value = heap[1];
//把堆尾元素前置，再sink(）调整
heap[1]=heap[hs--];
sink(1);
cout<<hs<<endl;
for(int i=1;i<=hs;i++)cout<<heap[i]<<" ";
cout<<endl;
return value;
}
/*****************************************************************/
//下沉函数，辅助实现删除操作deleteMin()
void sink(int fa){
int son = fa<<1,a = heap[fa];
while(son<=hs){
//使得son为两儿子中的较小值
if(son<hs&&heap[son+1]<heap[son])
son=son+1;
// 说明此时“fa”的位置很稳定
if(a<=heap[son])//千万别写成heap[fa]<=heap[son] !!!
break;
//物理上，为值得覆盖，逻辑上为两值的swap交换
heap[fa] = heap[son];//son位置的数向上浮动
fa = son;//循环迭代，以现在的son位置作为新的fa位置
son = fa<<1;
}
heap[fa] = a;
}
/*****************************************************************/
//插入操作补充：综合编程 , 其他综合 ,上一个：数据结构与算法（4）——并查集
下一个：数据结构——堆排序
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络，
部分文章来自网络，