|
#include <stdio.h>
#define SIZE 10
#define Left(i) ((i) << 1)
#define Right(i) (((i) << 1) + 1)
void heapsort(int a[], int heapsize);
void maxheapify(int a[], int i, int heapsize);
void swap(int *x, int *y);
int main(int argc, char **argv)
{
int a[SIZE+1] = { 0, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };
/* note a[0] is not used */
int i, heapsize;
heapsize = SIZE;
heapsort(a, heapsize);
for (i = 1; i < SIZE + 1; i++) /* print the sorted array */
printf("%d ", a[i]);
printf("\n");
return 0;
}
/*
* heapsort: contains two procedures, one is to build the max-heap,
* the other is to delete max to gain the sorted array.
*/
void heapsort(int a[], int heapsize)
{
int i;
for (i = heapsize / 2; i >= 1; i--) /* build max-heap */
maxheapify(a, i, heapsize);
for (i = heapsize; i >= 2; i--) /* delete max */
{
swap(&a[1], &a[i]);
heapsize--;
maxheapify(a, 1, heapsize);
}
}
/*
* maxheapify: used to let the value at a[i] "float down" in the
* max-heap so that the subtree rooted at index i becomes a max-heap.
*/
void maxheapify(int a[], int i, int heapsize)
{
int largest, left, right;
left = Left(i);
right = Right(i);
if (left <= heapsize && a[left] > a[i])
largest = left;
else
largest = i;
if (right <= heapsize && a[right] > a[largest])
largest = right;
if (largest != i)
{
swap(&a[i], &a[largest]);
maxheapify(a, largest, heapsize); /* recurrsion */
}
return; /* return when largest == i */
}
void swap(int *x, int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
|
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
评论人