堆排序的问题高手进
发布网友
发布时间：2022-04-25 05:19
共1个回答
热心网友
时间：2023-10-29 10:03
#define LEFT(i) 2*i
#define RIGHT(i) 2*i+1
/***********以下为堆排序**********/
void MAX_HEAPIFY(keytype *a,int i,int size)
//保持堆的性质，使以i为根的子树成为最大堆
//过程描述：
/*
从元素a[i],a[left(i)],a{right(i)]中找出最大的，并将其下标保存在largest中。如果a[i]是最大的，则以i为根的子树以是最大堆，程序结束。否则，i的某个子结点中有最大元素，则交换a[i]与a[largest],从而使i及其子女满足堆性质。下标为largest的结点在交换后的值是a[i],以该结点为根的子树又有可能违反最大堆性质，因而要迭代这个过程。
*/
{
int largest=-1;
for(;;i=largest)
{
int l=LEFT(i),r=RIGHT(i);
if(l<=size&&a[l-1]>a[i-1])
largest=l;
else
largest=i;
if(r<=size&&a[r-1]>a[largest-1])
largest=r;
if(largest==i)break;
swap(&a[i-1],&a[largest-1]);
}
}
void BUILD_MAX_HEAP(keytype *a,int size)
//子数组a[size/2+1]...a[size]的元素都是叶子，所以只对前面的元素保持堆的性质即可完成建堆
{
int i=size/2;
while(i>=1)
{
MAX_HEAPIFY(a,i--,size);
}
}
void HeapSort(keytype *a,int size)//排序调用函数
{
int i=size;
BUILD_MAX_HEAP(a,size);//先建最大堆
for(;i>=2;--i)//不断的把堆的根即最大元素放到数组尾部并缩小堆的大小，然后再保持堆的性质，迭代这一过程，从而实现升序排列
{
swap(&a[i-1],&a[0]);
--size;
MAX_HEAPIFY(a,1,size);
}
}
以上是我写的堆排序，原理都是一样的，但是结构应该是要清晰一点吧
