c语言实现最大堆

以我实现的经验来看&＃xff0c;还是快点学会c&＃43;&＃43;吧&＃xff0c;c语言来写的话&＃xff0c;太复杂了。。。注意点我都标记在了代码里&＃xff0c;然后&＃xff0c;想提醒自己一下&＃xff0c;插入是&＃xff0c;调整堆&＃xff0c;是循环上移&＃xff1b;删除时&＃xff0c;调整堆&＃xff0c;是循环下移

这里由于初次学习&＃xff0c;就先将二叉堆不打印成树的形状&＃xff0c;只是以数组的形式输出&＃xff0c;等进阶了&＃xff0c;再来思考一下

//c语言实现一个最大堆. 堆从数组的下标为1的部分开始存储
//写的时候不得不感叹&＃xff0c;还是c&＃43;&＃43;强大啊&＃xff0c;真的更安全了#include
#include
#include
#include#define INIT_SIZE 100
#define INCREASE_SIZE 10
#define true 1
#define false 0typedef struct
{int* data; //实现一个可以动态扩展容量的堆int size; //堆内元素的个数int capacity;}Maxheap;void swap(int * a,int *b)
{int temp;temp &＃61; *a;*a &＃61; *b;*b &＃61; temp;
}void Init_Maxheap(Maxheap* max_heap)
{max_heap->data &＃61; (int*)malloc( INIT_SIZE * sizeof(int) );assert(max_heap->data);max_heap->size &＃61; 0;max_heap->capacity &＃61; INIT_SIZE;}int Is_Empty(Maxheap max_heap)
{return max_heap.size &＃61;&＃61; 0 ? true : false;}//这里的循环要理解 曾经写错过
void Insert_Maxheap(Maxheap* max_heap,int e)
{//先判断数组空间是否够if(max_heap->size &＃43;1 > INIT_SIZE){//注意 realloc写法max_heap->data &＃61; (int*)realloc(max_heap->data,(INIT_SIZE &＃43; INCREASE_SIZE) *sizeof(int));assert(max_heap->data);max_heap->capacity &＃43;&＃61; INCREASE_SIZE;}//不要忘记改变size的值啊&＃xff0c;因为就是通过它来访问堆max_heap->size &＃43;&＃43;;int j &＃61; max_heap->size;max_heap->data[j] &＃61; e;//将插入的元素上移的过程//这里是while 而不是if 有索引就要考虑越界。注意这是一个循环上移的过程while( j > 1 && max_heap->data[ j/2 ] data[j]) //注意这里不能写e哦&＃xff0c;因为循环每一次这个值都是改变的{swap(&max_heap->data[j/2],&max_heap->data[j]); j &＃61; j/2;}}//这里的循环要理解 曾经写错过。注意这是一个循环下移的过程
int Extract_Maxheap(Maxheap* max_heap)
{assert(max_heap->size > 0);int ret &＃61; max_heap->data[1];//这里我们让最后一个元素直接赋值到第一个元素&＃xff0c;然后size-- 下一次插入元素的时候就直接将其覆盖即可max_heap->data[1] &＃61; max_heap->data[max_heap->size]; //可以看出来用c来写有点麻烦啊max_heap->size --;//然后来从上到下调整堆//当它没有孩子的时候就不循环了 由于是从上往下的&＃xff0c;每一次父节点值会有所变化&＃xff0c;其初始值为1int k &＃61; 1;while(k * 2 <&＃61; max_heap->size ) //有左孩子就证明有孩子{//看它是否有右孩子 并比较左右孩子值的大小int exchange &＃61; 2 * k;if(exchange &＃43; 1 <&＃61; max_heap->size && max_heap->data[exchange&＃43;1] > max_heap->data[exchange])exchange &＃43;&＃61; 1;//这个思考漏掉了if(max_heap->data[k] > max_heap->data[exchange])break;swap(&max_heap->data[k],&max_heap->data[exchange]);k &＃61; exchange; //注意这里要更改变化}return ret;
}void Print_Maxheap(Maxheap max_heap)
{for(int i &＃61; 1; i <&＃61; max_heap.size;i&＃43;&＃43;){printf("%d ",max_heap.data[i]);}printf("\n");
}int main(int argc, char const *argv[])
{Maxheap max_heap;Init_Maxheap(&max_heap);srand(time(NULL));for(int i &＃61; 0; i <15 ; i&＃43;&＃43;)Insert_Maxheap(&max_heap,rand()%100);Print_Maxheap(max_heap);while(!Is_Empty(max_heap))printf("%d ", Extract_Maxheap(&max_heap));printf("\n");return 0;
}