Question

数据结构的堆排序

写出对应于序列（10，20，7，75，41，67，3，9，30，45）的初始堆（堆顶元素取最小值）。

Answer 1

堆排序（C语言版）2010-03-15 23:24/*简述：

所谓堆排序，就是就是将所要排序的数以二叉树的形式存储。其中，有根的元素值大于其孩子结点。一直递归下去，每当取出最大的元素，考量其左右子树，以保持其根节点最大的性质不变。这个算法的时间复杂性是O（n log2 n）。证明略。 */

#include<stdio.h>
#define max_size 10//数组元素个数
#include<stdlib.h>
int heap_size;//当前堆中的元素数目
void MAX_HEAPFY(int A[], int i) {
int left, right, temp, largest;
left = 2*i;//
right = 2*i + 1;
if( left <= heap_size && A[i] < A[left] )
largest = left;
else largest = i;
if( right <= heap_size && A[right] > A[largest])
largest = right;
if(largest != i) {
temp = A[i];
A[i] = A[largest];
A[largest] = temp;
MAX_HEAPFY(A, largest);
}
}
void BUILD_MAX_HEAP(int A[]) {
//这个函数是用来产生最大堆的
int i;
heap_size = max_size-1;
for( i = (max_size-1)/2; i != 0; i--) {
MAX_HEAPFY(A, i);
printf("*****\n");
}
}
void HEAP_SORT(int A[]) {
int i, temp;
BUILD_MAX_HEAP(A);
for( i = (max_size-1); i != 1; i--) {
temp = A[1];
A[1] = A[i];
A[i] = temp;
--heap_size;
MAX_HEAPFY(A, 1);
}
}
int main()
{
int i;
int A[max_size];
for(i = 1; i != max_size; i++) {
A[i] = rand() % max_size;
printf("%5d", A[i]);
}
HEAP_SORT( A );
printf("\n\n");
for(i = 1; i != max_size; i++)
printf("%5d",A[i]);
system("PAUSE");
}