c语言实现最大堆的基本功能

痛定思痛。 2022-05-15 12:28 123阅读 0赞

**最大堆的声明:**

typedef struct{
    	int *data;
    	int size;
    	int capacity;
    }heap,*Maxheap;

注意:（1）.用一个数组存放最大堆，用int \*data声明数组

（2）.size表示当前容量，capacity表示最大容量

**最大堆的创建:**

Maxheap create(int MaxSize){
    	Maxheap h=(Maxheap)malloc(sizeof(heap));
    	h->data=(int *)malloc((MaxSize+1)*sizeof(int));
    	h->size=0;
    	h->capacity=MaxSize;
    	h->data[0]=MAXDATA;
    	return h;
    }

注意:（1）.data数组是用指针声明的，所以需要分配内存空间，因为还要有一个哨兵，所以（maxsize+1）\*sizeof（int）就是总字节数，最后转换为int \*

（2）.一开始没数据，size为0，哨兵不算，哨兵存放在索引为0的位置

**最大堆的插入:**

void insert(Maxheap h,int x){
    	int i;
    	if(isFull(h)){
    		printf("full\n");
    		return;
    	}
    	i=++h->size;
    	for(;h->data[i/2]<x;i/=2){
    		h->data[i]=h->data[i/2];
    	}
    	h->data[i]=x;
    }

注意:（1）.i=++h->size是先加再用值（++i），i++是先用值再加

(2).for循环退出来的条件是h->data\[0\]>x，因为哨兵是一个很大的数

（3）.如果i/2的数比i小，就把小的放在下面，大的先不用放（因为大的位置要一直比较才能确定，用i表示大的数暂时的位置（i/=2）），最后确定好即是循环跳出之时(h->data\[i\]=x)

**最大堆的删除:**

int Delete(Maxheap h){
    	int parent,child;
    	if(h->size==0){
    		printf("最大堆为空，不能删除!");
    		return ;
    	}
    	int temp=h->data[h->size--];
    	int max=h->data[1];
    	for(parent=1;parent*2<=h->size;parent=child){
    		child=parent*2;
    		if((child!=h->size)&&(h->data[child]<h->data[child+1])){
    			child++;
    		}
    		if(temp>=h->data[child]){
    			break;
    		}else{
    			h->data[parent]=h->data[child];
    		}
    	}
    	h->data[parent]=temp;
    	return max;
    }

注意:（1）.删除首先把最顶部的元素挪走，然后假设把最后一个元素放上去（这样就保留了完全二叉树的结构），然后再调整每一个元素的位置

（2）.parent是最后一个元素的暂时位置，首先循环的条件是有儿子，才可以进行调动（parent\*2<=h->size）,然后取其儿子中最大的一个（有右儿子的前提是child！=h->size），然后temp比儿子们都大，证明parent假设temp的位置是正确的，如果比儿子们小，就把儿子放上去，自己暂时不能放，因为位置还不确定，然后parent=child表示修改temp暂时的位置，最后循环跳出的条件是没有儿子，此时再确定temp位置才是准确的

**最大堆的调整:**

void PercDown(Maxheap h,int i){
    	int x=h->data[i];
    	int parent,child;
    	for(parent=i;(parent*2)<=h->size;parent=child){
    			child=parent*2;
    			if((child!=h->size)&&(h->data[child]<h->data[child+1])){
    				child++;
    			}
    			if(x>=h->data[child]){
    				break;
    			}else{
    				h->data[parent]=h->data[child];
    			}
    	}
    	h->data[parent]=x;
    
    }
    void BuildHeap(Maxheap h){
    	int i;
    	for(i=h->size/2;i>0;i--){
    		PercDown(h,i);
    	}
    }

注意:（1）.怎么把散乱的完全二叉树调整成最大堆呢？首先要从最后一个元素的父节点开始调整，依次i--进行调整，第一个元素也要调整(所以i>0)

（2）.怎么调整呢？首先x是父元素（即索引为i的元素），如果父元素比儿子们大，就不用调整，如果儿子们大，就把大的儿子放上去，自己暂时不能放下去（因为位置还不确定，要一直比较），parent表示父元素暂时的位置，直到父元素比儿子们大或者父元素没有儿子，就跳出循环，此时位置也确定了，就把往该位置插入元素