数据结构----堆(2)
堆1中介绍了堆的定义性质以及建堆过程，这篇主要介绍堆排序以及堆的一种应用---优先级队列
1、堆排序
堆排序算法，先用build_max_heap将输入数组A[0,...,n-1]建立一个最大堆。因为数组中最大元素在A[0],则可以通过交换A[0]和A[n-1],此时将最大数A[n-1]存入结果数组result中，并将此节点去掉，此时数组就剩下A[0,...,n-2],由于互换，新的根元素可能违背了最大堆的性质，此时再调用建堆子程序Max_heapify(A,0)保持此性质，在A[0,...,n-2]中构造最大堆。不断递归这个过程，堆的大小从n-1降到1。c语言程序如下：//堆排序
//返回nums中具有最大关键字的元素int maximum(int nums[],int len){ return nums[0];}//去掉，并返回nums中具有最大关键字的元素int extract_max(int nums[],int len){ if(len<1){ cout<<"error:heap underflow"<<endl;}int max=nums[0];nums[0]=nums[len-1];nums[len-1]=NULL;max_heapify2(nums,len-1,0);return max;}//将nums[index]的关键字的值增加到key，增加后将其移到合适的位置，使其满足最大堆void increase_key(int nums[],int len,int index,int key){if(key<nums[index]){ cout<<"error:new key is smaller than current key"<<endl;}nums[index]=key;int parent_index=(index-1)/2;int temp=0;while(index>=0&&nums[index]>nums[parent_index]){//类似插入排序 temp=nums[index]; nums[index]=nums[parent_index]; nums[parent_index]=temp; index=parent_index; parent_index=(index-1)/2;} }//将x插入最大堆的适合位置，首先加入负无穷的叶子节点，然后调用increase_key()设置新节点的值并移到合适位置void insert(int nums[],int len,int x){ int key=INT_MIN; nums=(int *)realloc(nums,len+1); nums[len]=key; increase_key(nums,len+1,len,x);}?分析四种操作：第一种操作：O(1)第2、3、4操作：O(log2^n)
?
?